题目描述：

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

Examples: 

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

题目大意：

给定一个只包含数字0-9的字符串以及一个目标值，通过在数字之间添加+, -, *运算符，使得运算结果等于目标值，返回所有可能的组合方案。

测试用例见题目描述。

解题思路：

DFS（深度优先搜索）

将字符串拆解成left + operator + right的形式，针对left执行递归

注意：包含前导0的运算数是无效的。

例如，通过"00+9"获得目标值9是不正确的。

Python代码：

class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        def isLeadingZeros(num):
            return num.startswith('00') or int(num) and num.startswith('0')
        def solve(num, target, mulExpr = '', mulVal = 1):
            ans = []
            #remove leading zeros
            if isLeadingZeros(num):
                pass
            elif int(num) * mulVal == target:
                ans += num + mulExpr,
            for x in range(len(num) - 1):
                lnum, rnum = num[:x+1], num[x+1:]
                #remove leading zeros
                if isLeadingZeros(rnum):
                    continue
                right, rightVal = rnum + mulExpr, int(rnum) * mulVal
                #op = '+'
                for left in solve(lnum, target - rightVal):
                    ans += left + '+' + right,
                #op = '-'
                for left in solve(lnum, target + rightVal):
                    ans += left + '-' + right,
                #op = '*'
                for left in solve(lnum, target, '*' + right, rightVal):
                    ans += left,
            return ans
        if not num:
            return []
        return solve(num, target)

 

本文链接：http://bookshadow.com/weblog/2015/09/16/leetcode-expression-add-operators/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码