241. Different Ways to Add Parentheses

Problem Description

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

The test cases are generated such that the output values will fit in a 32-bit integer and the number of different results won't exceed 10⁴.

Example 1:

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

Example 2:

Input: expression = "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

Constraints:

• 1 <= expression.length <= 20
• expression consists of digits and the operator '+', '-', and '*'
• All the integer values in the input expression are in the range [0, 99]

Python Solution

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        # If expression is a number, return it
        if expression.isdigit():
            return [int(expression)]
        
        results = []
        for i in range(len(expression)):
            if expression[i] in "+-*":
                # Split expression at operator
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i+1:])
                
                # Combine results from left and right
                for l in left:
                    for r in right:
                        if expression[i] == '+':
                            results.append(l + r)
                        elif expression[i] == '-':
                            results.append(l - r)
                        else:  # '*'
                            results.append(l * r)
                            
        return results

Java Solution

class Solution {
    public List diffWaysToCompute(String expression) {
        List results = new ArrayList<>();
        
        // If expression is a number, return it
        boolean isNumber = true;
        for (char c : expression.toCharArray()) {
            if (!Character.isDigit(c)) {
                isNumber = false;
                break;
            }
        }
        if (isNumber) {
            results.add(Integer.parseInt(expression));
            return results;
        }
        
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                // Split expression at operator
                List left = diffWaysToCompute(expression.substring(0, i));
                List right = diffWaysToCompute(expression.substring(i + 1));
                
                // Combine results from left and right
                for (int l : left) {
                    for (int r : right) {
                        if (c == '+') {
                            results.add(l + r);
                        } else if (c == '-') {
                            results.add(l - r);
                        } else {  // '*'
                            results.add(l * r);
                        }
                    }
                }
            }
        }
        
        return results;
    }
}

C++ Solution

class Solution {
public:
    vector diffWaysToCompute(string expression) {
        vector results;
        
        // If expression is a number, return it
        bool isNumber = true;
        for (char c : expression) {
            if (!isdigit(c)) {
                isNumber = false;
                break;
            }
        }
        if (isNumber) {
            results.push_back(stoi(expression));
            return results;
        }
        
        for (int i = 0; i < expression.length(); i++) {
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
                // Split expression at operator
                vector left = diffWaysToCompute(expression.substr(0, i));
                vector right = diffWaysToCompute(expression.substr(i + 1));
                
                // Combine results from left and right
                for (int l : left) {
                    for (int r : right) {
                        if (c == '+') {
                            results.push_back(l + r);
                        } else if (c == '-') {
                            results.push_back(l - r);
                        } else {  // '*'
                            results.push_back(l * r);
                        }
                    }
                }
            }
        }
        
        return results;
    }
};

JavaScript Solution

/**
 * @param {string} expression
 * @return {number[]}
 */
var diffWaysToCompute = function(expression) {
    // If expression is a number, return it
    if (!isNaN(expression)) {
        return [parseInt(expression)];
    }
    
    const results = [];
    
    for (let i = 0; i < expression.length; i++) {
        const char = expression[i];
        if (char === '+' || char === '-' || char === '*') {
            // Split expression at operator
            const left = diffWaysToCompute(expression.slice(0, i));
            const right = diffWaysToCompute(expression.slice(i + 1));
            
            // Combine results from left and right
            for (const l of left) {
                for (const r of right) {
                    if (char === '+') {
                        results.push(l + r);
                    } else if (char === '-') {
                        results.push(l - r);
                    } else {  // '*'
                        results.push(l * r);
                    }
                }
            }
        }
    }
    
    return results;
};

C# Solution

public class Solution {
    public IList DiffWaysToCompute(string expression) {
        var results = new List();
        
        // If expression is a number, return it
        bool isNumber = true;
        foreach (char c in expression) {
            if (!char.IsDigit(c)) {
                isNumber = false;
                break;
            }
        }
        if (isNumber) {
            results.Add(int.Parse(expression));
            return results;
        }
        
        for (int i = 0; i < expression.Length; i++) {
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
                // Split expression at operator
                var left = DiffWaysToCompute(expression.Substring(0, i));
                var right = DiffWaysToCompute(expression.Substring(i + 1));
                
                // Combine results from left and right
                foreach (int l in left) {
                    foreach (int r in right) {
                        if (c == '+') {
                            results.Add(l + r);
                        } else if (c == '-') {
                            results.Add(l - r);
                        } else {  // '*'
                            results.Add(l * r);
                        }
                    }
                }
            }
        }
        
        return results;
    }
}