Different Ways to Add Parentheses
Medium · 1-D Dynamic Programming · Explanation and code example
Memoized Expression Splitting
How it works
Each operator can be the final operation in a parenthesization. Recursively obtain every result for its left and right substrings, combine every pair with that operator, and memoize substring results. A substring without an operator is a numeric base case.
Steps
- Split at each +, -, or * operator.
- Combine all left and right results for that split.
- Cache the result list; parse the number when no split exists.
Complexity
- Time: Output-sensitive and exponential in the number of operators; there are Catalan-many parenthesizations, with substring work as well.
- Space: Exponential result storage plus recursion and substring copies.
Things to watch for
- Preserve duplicate results from different parenthesizations.
- Parse multi-digit numeric leaves as a whole.
- Apply arithmetic directly rather than evaluating arbitrary text.
Python code example
import functools
class Solution:
@functools.lru_cache(None)
def diffWaysToCompute(self, expression: str) -> list[int]:
ans = []
for i, c in enumerate(expression):
if c in '+-*':
for a in self.diffWaysToCompute(expression[:i]):
for b in self.diffWaysToCompute(expression[i + 1:]):
ans.append(a + b if c == '+' else a - b if c == '-' else a * b)
return ans or [int(expression)]
C++ code example
class Solution {
public:
vector<int> diffWaysToCompute(string expression) {
return ways(expression, {});
}
private:
vector<int> ways(const string& s, unordered_map<string, vector<int>>&& mem) {
if (const auto it = mem.find(s); it != mem.cend())
return it->second;
vector<int> ans;
for (int i = 0; i < s.length(); ++i)
if (ispunct(s[i]))
for (const int a : ways(s.substr(0, i), std::move(mem)))
for (const int b : ways(s.substr(i + 1), std::move(mem)))
if (s[i] == '+')
ans.push_back(a + b);
else if (s[i] == '-')
ans.push_back(a - b);
else
ans.push_back(a * b);
return mem[s] = (ans.empty() ? vector<int>{stoi(s)} : ans);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.