Problem statement

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

Solution 1

First, split string into numbers and operators. Let dp[i][j] be all possible solutions for numbers between i and j. Then we start with diagonal and then for every k between i and j we use dp[i][k] and dp[k+1][j] to construct p[i][j].

Complexity

Potential complexity O(C_n * n), where n is length of numbers and C_n is Catalan number.

Code

class Solution:
    def diffWaysToCompute(self, inp):
        nums = inp.replace("*", " ").replace("-", " ").replace("+", " ").split()
        signs = [elem for elem in inp if elem in "*-+"]
        n = len(nums)
        
        dp = [[[] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i].append(int(nums[i]))

        for j in range(1, n):
            for i in range(0, n-j):
                for k in range(i, i + j):
                    for sol1 in dp[i][k]:
                        for sol2 in dp[k+1][i+j]:
                            if signs[k] == "+":
                                dp[i][i+j].append(sol1 + sol2) 
                            if signs[k] == "-":
                                dp[i][i+j].append(sol1 - sol2) 
                            if signs[k] == "*":
                                dp[i][i+j].append(sol1 * sol2) 
        
        return dp[0][n-1]

Solution 2

We can use the same idea but with lru_cache for memoisation.

Complexity

It is the same as in previous approach.

Code

class Solution:
    def diffWaysToCompute(self, inp):
        nums = inp.replace("*", " ").replace("-", " ").replace("+", " ").split()
        signs = [elem for elem in inp if elem in "*-+"]
        funcs = {"+": lambda x, y: x+y, "-": lambda x, y: x-y, "*": lambda x, y: x*y}
        n = len(nums)
        
        @lru_cache(None)
        def dp(i, j):
            if i == j: return (int(nums[i]),)
            ans = []
            for k in range(i, j):
                for sol1, sol2 in product(dp(i, k), dp(k+1, j)):
                    ans.append(funcs[signs[k]](sol1, sol2))
            return tuple(ans)
        
        return dp(0, n-1)