Fast Python Solution with a dictionary


  • 0
    S
    class Solution(object):
        def diffWaysToCompute(self, input):
            """
            :type input: str
            :rtype: List[int]
            """
            dic = {}
            return getSums(input, dic)
    
    def getSums(string, dic):
        
        res = []
        sign = False
        if string in dic:
            return dic[string]
        for i in range(len(string)):
            if string[i] == "+" or string[i] == "-" or string[i] == "*":
                sign = True
                fore = string[:i]
                after = string[i+1:]
                foreSums = getSums(fore, dic)
                afterSums = getSums(after, dic)
                for foreSum in foreSums:
                    for afterSum in afterSums:
                        r = compute(foreSum, string[i], afterSum)
                        res.append(r)
                        dic[string] = res
        if not sign:
            return [int(string)]
        return res
    
    def compute(a, sign, b):
        if sign == "+":
            return a+b
        elif sign == "-":
            return a-b
        else:
            return a*b

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.