[LeetCode]Different Ways to Add Parentheses

题目描述:

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

题目大意:

给定一个包含数字和运算符的字符串,返回所有对数字与运算符分组可能得到的计算结果。有效的运算符为 +, - 和 *

测试样例见题目描述。

解题思路:

解法I 分治法(Divide and conquer)

递归地将表达式按照运算符拆分为左右两半

类Python伪码:

def solve(input):
    if input is digit:
        return [input]
    ans = [ ]
    for x in input:
        if x is operator:
            left = solve(input[0 ~ x])
            right = solve(input[x + 1 ~ len])
            for l in left:
                for r in right:
                    ans += [ calc(l, r, x) ]
    return ans

Python代码:

class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        if input.isdigit(): return [int(input)]
        result = []
        for i, c in enumerate(input):
            if c in '+-*':
                left = self.diffWaysToCompute(input[:i])
                right = self.diffWaysToCompute(input[i+1:])
                for l in left:
                    for r in right:
                        result.append(eval(str(l) + c + str(r)))
        return result

上述解法可以通过记忆化进行加速。

Python代码:

class Solution(object):
    def __init__(self):
        self.cache = collections.defaultdict(list)
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        if input.isdigit(): return [int(input)]
        if input in self.cache: return self.cache[input]
        result = []
        for i, c in enumerate(input):
            if c in '+-*':
                left = self.diffWaysToCompute(input[:i])
                right = self.diffWaysToCompute(input[i+1:])
                for l in left:
                    for r in right:
                        result.append(eval(str(l) + c + str(r)))
        self.cache[input] = result
        return result

解法II 回溯法(Backtracking),时间复杂度O(n!),n为运算符的个数

通过dict保存有效的加括号方案,使用内置函数expr计算结果

Python代码:

class Solution:
    # @param {string} input
    # @return {integer[]}
    def diffWaysToCompute(self, input):
        exprDict = dict()
        def dfs(nums, ops):
            if ops:
                for x in range(len(ops)):
                    dfs(nums[:x]+['('+nums[x]+ops[x]+nums[x+1]+')']+nums[x+2:],ops[:x]+ops[x+1:])
            elif nums[0] not in exprDict:
                exprDict[nums[0]] = eval(nums[0])
        nums, ops = [], []
        input = re.split(r'(\D)', input)
        for x in input:
            if x.isdigit():
                nums.append(x)
            else:
                ops.append(x)
        dfs(nums, ops)
        return exprDict.values()

另附一段简洁的Python代码,学习一下:

摘自LeetCode Discuss:https://leetcode.com/discuss/48468/11-lines-python

Solution 1 - 48 ms

class Solution:
    # @param {string} input
    # @return {integer[]}
    def diffWaysToCompute(self, input):
        tokens = re.split('(\D)', input)
        nums = map(int, tokens[::2])
        ops = map({'+': operator.add, '-': operator.sub, '*': operator.mul}.get, tokens[1::2])
        def build(lo, hi):
           if lo == hi:
               return [nums[lo]]
           return [ops[i](a, b)
                   for i in xrange(lo, hi)
                   for a in build(lo, i)
                   for b in build(i + 1, hi)]
        return build(0, len(ops))

Solution 2 - 168 ms

class Solution:
    # @param {string} input
    # @return {integer[]}
    def diffWaysToCompute(self, input):
        return [eval(`a`+c+`b`)
            for i, c in enumerate(input) if c in '+-*'
            for a in self.diffWaysToCompute(input[:i])
            for b in self.diffWaysToCompute(input[i+1:])] or [int(input)]

Solution 3 - 64 ms

class Solution:
    # @param {string} input
    # @return {integer[]}
    def diffWaysToCompute(self, input):
        return [a+b if c == '+' else a-b if c == '-' else a*b
            for i, c in enumerate(input) if c in '+-*'
            for a in self.diffWaysToCompute(input[:i])
            for b in self.diffWaysToCompute(input[i+1:])] or [int(input)]

 

本文链接:http://bookshadow.com/weblog/2015/07/27/leetcode-different-ways-add-parentheses/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论