[LeetCode]Expression Add Operators

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. 丁香 丁香 发布于 2015年9月22日 04:15 #

    请问时间复杂度是多少,看起来是指数级,O(4^n)吗?
    有没有多项式时间复杂度的解法?

  2. 在线疯狂 在线疯狂 发布于 2015年9月22日 15:53 #

    没错,是指数级的,暂时没有找到多项式阶时间复杂度的解法。。。

  3. mach7 mach7 发布于 2015年10月13日 08:56 #

    yuan lai python dai ma hai neng zhe me xie, xue xi le...

  4. persiangarfield persiangarfield 发布于 2015年10月18日 14:54 #

    既然要返回所有可能答案,不枚举个4^n的时间也搞不定吧…

  5. null null 发布于 2016年4月30日 12:59 #

    numval有什么特殊意义吗?

张贴您的评论