Python solution with detailed explanation


  • 0
    G

    Solution

    Different Ways to Add Parentheses https://leetcode.com/problems/different-ways-to-add-parentheses/

    Divide and Conquer Algorithm

    • Split the input at an operator. Evaluate the left half, evaluate the right half, and then merge the two.
    • Base condition is when input has no operator, simply return the integer equivalent of the input.
    class Solution(object):
        def diffWaysToCompute(self, input):
            return self.helper(input)
        
        def merge(self, left, right, x, result):
            eval_method = {"+": lambda x,y: x+y, "-": lambda x,y: x-y, "*": lambda x,y: x*y}
            for a in left:
                for b in right:
                    result.append(eval_method[x](a, b))
            return
        
        def helper(self, expr):
            """
            :type input: str
            :rtype: List[int]
            """
            result = []
            if "+" not in expr and "-" not in expr and "*" not in expr:
                return [int(expr)]
            for i, x in enumerate(expr):
                if x in ("+", "-", "*"):
                    left, right = self.helper(expr[0:i]), self.helper(expr[i+1:])
                    self.merge(left, right, x, result)
            return result
    

Log in to reply
 

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