[LeetCode] 241. Different Ways to Add Parentheses

Problem : https://leetcode.com/problems/different-ways-to-add-parentheses/

Use divide-and-conquer approach to split the expression into 2 sub-expression.

Continue split the expression until encounter the expression only contains 1 single number.

class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        
        def getExpression():
            expression = []
            i = 0
            while i < len(input):
                if input[i].isalnum():
                    num = 0

                    while i < len(input) and input[i].isalnum():
                        num = num * 10 + int(input[i])
                        i += 1

                    expression.append(num)
                else:
                    expression.append(input[i])
                    i += 1
                    
            return expression
            
        
         
        def compute(a, opt, b):
            if opt == '+':
                return a + b
            
            if opt == '-':
                return a - b
            
            if opt == '*':
                return a * b
            
            return a // b
            
            
        def helper(expression, start, end):
            if end - start == 1:
                return [expression[start]]
            
            if end - start == 3:
                return [compute(expression[start], expression[start+1], expression[start+2])]
            
            result = []
            
            for i in range(start+1, end):
                opt = expression[i-1]
                
                if type(opt) != str:
                    continue
                    
                for a in helper(expression, start, i-1):
                    for b in helper(expression, i, end):
                        result.append(compute(a, opt, b))
                                
            return result
        
        expression = getExpression()
        return helper(expression, 0, len(expression))