241. Different Ways to Add Parentheses – Leetcode Solutions

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

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        # Helper function to check if the input is a digit
        if expression.isdigit():
            return [int(expression)]  # If the expression is a single number, return it as the result
        
        results = []  # This will store all the possible results
        
        # Iterate through each character in the expression
        for i in range(len(expression)):
            char = expression[i]
            
            # If the current character is an operator, split the expression into two parts
            if char in ['+', '-', '*']:
                # Recursively compute the results of the left and right parts
                left_part_results = self.diffWaysToCompute(expression[:i])  # Left sub-expression
                right_part_results = self.diffWaysToCompute(expression[i+1:])  # Right sub-expression
                
                # Combine the results from left and right parts using the current operator
                for left_result in left_part_results:
                    for right_result in right_part_results:
                        if char == '+':
                            results.append(left_result + right_result)  # Apply addition
                        elif char == '-':
                            results.append(left_result - right_result)  # Apply subtraction
                        elif char == '*':
                            results.append(left_result * right_result)  # Apply multiplication
        
        # Return the final results list with all possible outcomes
        return results

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    // Function to compute all possible results from different groupings of numbers and operators
    vector<int> diffWaysToCompute(string expression) {
        // Base case: if the expression is purely a number, return it as the result
        if (isNumber(expression)) {
            return {stoi(expression)};
        }

        vector<int> results;

        // Loop through the expression to find operators and split the expression around them
        for (int i = 0; i < expression.size(); ++i) {
            char ch = expression[i];

            // Check if the character is an operator
            if (ch == '+' || ch == '-' || ch == '*') {
                // Recursively solve for the left and right parts of the expression
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                vector<int> right = diffWaysToCompute(expression.substr(i + 1));

                // Combine the results from left and right subexpressions using the current operator
                for (int l : left) {
                    for (int r : right) {
                        // Depending on the operator, calculate the result and add to the results list
                        if (ch == '+') {
                            results.push_back(l + r);
                        } else if (ch == '-') {
                            results.push_back(l - r);
                        } else if (ch == '*') {
                            results.push_back(l * r);
                        }
                    }
                }
            }
        }

        return results;
    }

private:
    // Helper function to check if a string is a number
    bool isNumber(const string& s) {
        for (char ch : s) {
            if (!isdigit(ch)) {
                return false;  // If any character is not a digit, return false
            }
        }
        return true;
    }
};

var diffWaysToCompute = function(expression) {
    // Helper function to check if the expression is purely a number
    function isNumber(expr) {
        // A string is purely a number if all characters are digits
        for (let char of expr) {
            if (isNaN(char)) {
                return false;
            }
        }
        return true;
    }

    // Base case: if the expression is just a number, return it as an integer in an array
    if (isNumber(expression)) {
        return [parseInt(expression)];
    }

    let results = [];

    // Loop through each character in the expression
    for (let i = 0; i < expression.length; i++) {
        let char = expression[i];

        // If the character is an operator ('+', '-', '*'), split the expression
        if (char === '+' || char === '-' || char === '*') {
            // Recursively compute all possible results for the left and right subexpressions
            let leftResults = diffWaysToCompute(expression.slice(0, i));
            let rightResults = diffWaysToCompute(expression.slice(i + 1));

            // Combine the results from the left and right subexpressions using the current operator
            for (let left of leftResults) {
                for (let right of rightResults) {
                    if (char === '+') {
                        results.push(left + right); // Add if the operator is '+'
                    } else if (char === '-') {
                        results.push(left - right); // Subtract if the operator is '-'
                    } else if (char === '*') {
                        results.push(left * right); // Multiply if the operator is '*'
                    }
                }
            }
        }
    }

    // Return the array containing all possible results
    return results;
};

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        // Base case: If the expression is just a number, return it as a single result
        if (isNumber(expression)) {
            List<Integer> result = new ArrayList<>();
            result.add(Integer.parseInt(expression));
            return result;
        }

        List<Integer> results = new ArrayList<>();

        // Iterate over each character in the expression
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);

            // If the character is an operator, split the expression
            if (ch == '+' || ch == '-' || ch == '*') {
                // Recursively compute results for the left and right subexpressions
                List<Integer> leftResults = diffWaysToCompute(expression.substring(0, i));
                List<Integer> rightResults = diffWaysToCompute(expression.substring(i + 1));

                // Combine the results of the left and right subexpressions using the operator
                for (int left : leftResults) {
                    for (int right : rightResults) {
                        if (ch == '+') {
                            results.add(left + right); // Add if the operator is '+'
                        } else if (ch == '-') {
                            results.add(left - right); // Subtract if the operator is '-'
                        } else if (ch == '*') {
                            results.add(left * right); // Multiply if the operator is '*'
                        }
                    }
                }
            }
        }

        return results;
    }

    // Helper function to check if the input string is a number
    private boolean isNumber(String s) {
        // A string is a number if all characters are digits
        for (char ch : s.toCharArray()) {
            if (!Character.isDigit(ch)) {
                return false;
            }
        }
        return true;
    }
}