0282._Expression_Add_Operators.md

282. Expression Add Operators

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/expression-add-operators/

内容描述

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"] 
Example 2:

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]
Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]
Example 4:

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]
Example 5:

Input: num = "3456237490", target = 9191
Output: []

解题方案

思路 1 - 时间复杂度: O(4^n)- 空间复杂度: O(N)******

我们要注意的是一个式子不能以'+','-','*'开头

第二点是不能出现以‘0’开头的数字

beats 46.74%

有时候在Python3中提交会超时，不知道是不是服务器原因

因为对于每一个digit，我们可以在它前面添加'+', '-', '*'或者什么也不加（注意上面提到过的两点），所以总的时间为O(4^N)

参考simple Python DFS that beats 100%

class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        def dfs(remain, cur_str, cur, prev):
            if not remain and cur == target:
                res.append(cur_str)
                
            for i in range(1, len(remain) + 1):
                if (i > 1 and remain[0] == '0'): # avoid '0X' number case be counted
                    return
                if len(cur_str) == 0:   # avoid generate str begin with +-*
                    dfs(remain[i:], remain[:i], int(remain[:i]), int(remain[:i]))
                else:
                    cur_num = remain[:i]
                    dfs(remain[i:], cur_str + '+' + remain[:i], cur + int(remain[:i]), int(remain[:i]))
                    dfs(remain[i:], cur_str + '-' + remain[:i], cur - int(remain[:i]), -int(remain[:i]))
                    # need take extra care for '*' case, a+b*c = a+b-b+b*c
                    dfs(remain[i:], cur_str+'*'+cur_num, cur-prev + prev*int(cur_num), prev*int(cur_num))
            
        res = []
        dfs(num, '', 0, 0)
        return res