algoadvance

Leetcode 241. Different Ways to Add Parentheses

Problem Statement

Given a string containing numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, -, and *.

Example:

Explanation:

((2-1)-1) = 0 
(2-(1-1)) = 2

Note:

Clarifying Questions

  1. Q: Can the input contain any other operators apart from +, -, and *? A: No, the input only contains numbers and the operators +, -, and *.

  2. Q: Are there any constraints on the size of the input string? A: While not specified, you can assume that it is small enough to devise a recursive solution.

  3. Q: Should the output numbers be unique? A: No, the output should contain all possible results, including duplicates if any.

  4. Q: Does operator precedence need to be considered? A: The goal is to compute results for all possible ways of grouping the numbers and operators, so typical operator precedence rules do not apply.

Strategy

  1. Divide and Conquer: To solve this problem, we can utilize a divide-and-conquer approach. We can split the expression at each operator and recursively calculate results for the left and right parts of the expression.
  2. Base Case: If the input is a single number (i.e., there are no operators left), return that number as the only result.
  3. Recursion: For each operator in the string, split the string into two parts: left and right. Recursively calculate results for both parts, and then combine these results using the current operator.
  4. Memoization: To avoid redundant calculations, use memoization to store results of already computed sub-expressions.

Code

import java.util.*;

public class Solution {
    // Memoization map to store results for sub-expressions
    private Map<String, List<Integer>> memo = new HashMap<>();

    public List<Integer> diffWaysToCompute(String input) {
        if (memo.containsKey(input)) {
            return memo.get(input);
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                String leftPart = input.substring(0, i);
                String rightPart = input.substring(i + 1);

                List<Integer> leftResults = diffWaysToCompute(leftPart);
                List<Integer> rightResults = diffWaysToCompute(rightPart);

                for (int left : leftResults) {
                    for (int right : rightResults) {
                        if (c == '+') {
                            result.add(left + right);
                        } else if (c == '-') {
                            result.add(left - right);
                        } else if (c == '*') {
                            result.add(left * right);
                        }
                    }
                }
            }
        }

        // Base case: if no operators found, it's a single number
        if (result.isEmpty()) {
            result.add(Integer.parseInt(input));
        }

        memo.put(input, result);
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.diffWaysToCompute("2-1-1"));
        System.out.println(sol.diffWaysToCompute("2*3-4*5"));
    }
}

Time Complexity

The time complexity of this solution is difficult to determine exactly due to the nature of recursion and repeated subproblem calculations. However, in the worst case, the complexity can be considered exponential, O(4^N / sqrt(N)), based on the number of ways to partition the expression.

This solution ensures that we efficiently compute all possible results by leveraging memoization to store and reuse already computed results.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI