Leetcode diary: 241. Different Ways to Add Parentheses
Tags: javascript, algorithms, devjournal, motivation
Published: 2022-01-11 08:26:44

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

[link](https://leetcode.com/problems/different-ways-to-add-parentheses/)  

This problem I just gave up after 15 minutes, there was just not enough information for me to continue. I kind of get that I could do recursion to get to the end, kind of like a DFS of a tree problem. However there were factors that I don't know if mattered, such as:
1.) is there any "invalid" parenthesis ?
2.) is there any "repeated" parenthesizing ?
3.) What is the general pattern of possible parenthesizing
4.) how could I calculate the result if I couldn't do something like parseInt("(2-1)-1") ? 

The solution from discussion:

```
const diffWaysToCompute = function(expression) {
    if(!expression.length) return [0];
    const result = [];
	
    for(let idx = 0; idx < expression.length; idx++){
        const char = expression[idx];
        if(char === "+" || char === "-" || char === "*"){
			//recurse
            const left = diffWaysToCompute(expression.substring(0, idx));
            const right = diffWaysToCompute(expression.substring(idx+1));
            //compute
            for(let leftVal of left){
                for(let rightVal of right){
                   switch(char){
                    case "+": result.push(parseInt(leftVal)+parseInt(rightVal)); break;
                    case "-": result.push(parseInt(leftVal)-parseInt(rightVal)); break;
                    default: result.push(parseInt(leftVal)*parseInt(rightVal)); break;
                    } 
                }
            }  
        }
    }
    if(!result.length) return [expression]
    return result
};
```

Now this is a doozy, so let me break it down to parts:
1.) The focal point of the iteration are not numbers, but the operation signs, this is alike [count-num-teams problem](https://leetcode.com/problems/count-number-of-teams). I really need to think outside the box when it comes to for loops, old habit die HARD ...

2.) Each operation is basically a first-child subtree (the full expression is the parent), and you just travel down to the leaf level of said subtree.

3.) whenever left and right comes back, you double nest for loop to run through all possible combinations of left and right via the current operation of iteration. 

This part is confusing, and you'll really need to run through the recursion from the bottom up to see how it works. Keep in mind that since the entire function is the recursion, I really don't like this style of coding, the result[] is a new array for each iteration. Therefore you just return the result[] in the end of recursion as well as for the final answer.

The lessons here:
1.) think outside of the box for for-loops if something isn't working out well
2.) be even more comfortable with recursion

Honestly I didn't beat up myself too hard for this question. Had I gotten this question in an interview, there would be questions that the interviewer could answer for me so I don't suffer as much. Pretty sure after home hinting I'd get the point of the problem is to basically get all possible permutation of the string. At this point, the recursion should be obvious and I'd get something pretty dang close to the answer.

Let me know anything on your mind after reading through this, THANKS!