Leetcode 241. Different Ways to Add Parentheses (Python)

Related Topic

Divide-And-Conquer.

Description

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 *.

Sample I/O

Example 1

Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2

Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(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

Methodology

This is a great question to practice the recursion. It solved by divide and conquer and the most difficult part is finding the pattern.

Let’s set example to show the pattern I found: Say if you got input 2-1-1+1, you can think it like a tree with root, left child and right child, every time when you read the operator you will split it into left part and right part:

1. Find the pattern:

   iteration 1:
			2 - 1- 1 + 1
		   /   \
		  2 - (1-1+1)
		 /	   /  \
		2	- (1 - (1+1))
		
		then
		
			2 - 1- 1 + 1
		   /   \
		  2 - (1-1+1)
		 /	     /  \
		2 - ((1 -1)+1)
		
This give us
1. 2- (1 - (1+1))=3
2. 2 - (1 -1)+1))=1


iteration 2:
		2 - 1 - 1 + 1
		    /   \
		(2 -1)-(1 + 1)
this give us
1. (2-1)-(1+1) = -1

iteration 3:
			2 - 1- 1 + 1
				   /   \
		   (2 - 1 - 1) + 1
			 / \          \
		   (2 - (1 -  1)) +  1
		   
		   then 
		   
		   2 - 1- 1 + 1
				   /   \
		   (2 - 1 - 1) + 1
			     / \      \
		 ((2 - 1) -  1) +  1
this give us
1.2 - (1 -  1)) +  1=3
2.((2 - 1) -  1) +  1=1

So the solution is [3,1,-1,3,1]

Code

def diffWaysToCompute(self, input: str) -> List[int]:
        if input.isdigit():
            return [int(input)]
        res = []
        for i in range(len(input)):
            if input[i] in "-+*":
                left = self.diffWaysToCompute(input[:i])
                right = self.diffWaysToCompute(input[i+1:])
                for l in left:
                    for r in right:
                        if input[i] == '+':
                            res.append(l+r)
                        elif input[i] == '-':
                            res.append(l-r)
                        elif input[i] == '*':
                            res.append(l*r)
        return res

BigO

We iterate all input list, it will cost O(n), each value we split into two parts, that cost O(logn), after that, we need to merge left and right in order to get answer so this give O(n), so total is(n^(logn+n)) which is n^2.