Divide and Conquer Algorithm: Operator Precedence
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 241. Different Ways to Add Parentheses | 🟠 |
In A Step-by-Step Guide to Binary Trees (Overview), I mentioned that there are two main approaches to recursive algorithms: the "traversal" approach and the "problem decomposition" approach. I noted that the typical example of the "traversal" approach is backtracking, while the "problem decomposition" approach is best represented by dynamic programming.
The reason dynamic programming is considered the typical example of the "problem decomposition" approach is mainly because it is more familiar to most people. However, many algorithmic problems do not have the overlapping subproblems and optimal substructure characteristics of dynamic programming problems, but can still be solved using the "problem decomposition" approach. We can give these algorithms a sophisticated name and collectively refer to them as "divide and conquer algorithms."
The most typical divide and conquer algorithm is Merge Sort, with the core logic as follows:
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
// ***** Divide *****
// Recursively sort the two halves of the array
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
// ***** Conquer *****
// Merge the two sorted subarrays
merge(nums, lo, mid, hi);
}"Sorting an Array" is an algorithmic problem that can be approached using the divide-and-conquer strategy. As long as I first sort the left half of the array, then sort the right half, and finally merge the two parts, isn't that sorting the entire array?
Let's look at a specific algorithmic problem.
All Ways to Add Parentheses
I'll use LeetCode problem #241 "Different Ways to Add Parentheses" to explain what a divide-and-conquer algorithm is. First, let's look at the problem:
241. Different Ways to Add Parentheses | LeetCode |
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 fit in a 32-bit integer and the number of different results does not exceed 104.
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 <= 20expressionconsists of digits and the operator'+','-', and'*'.- All the integer values in the input expression are in the range
[0, 99].
Simply put, you are given an arithmetic expression, and you can add parentheses to it in any way you like. Your task is to enumerate all possible ways to add parentheses and calculate the corresponding results.
The function signature is as follows:
// Calculate all the results with parentheses added
List<Integer> diffWaysToCompute(String input);// Calculate all results with parentheses added
std::vector<int> diffWaysToCompute(std::string input);# Calculate all the results with parentheses added
def diffWaysToCompute(input: str) -> List[int]:// Calculate all results with parentheses added
func diffWaysToCompute(input string) []int {
// your code here
}// Calculate all results with parentheses added
var diffWaysToCompute = function(input) {
};The first impression of this problem is likely to be complex. You might think you need to enumerate all possible ways to add parentheses, and consider the validity of the parentheses and the precedence of operations.
Yes, these need to be considered, but you don't have to worry about them. By using the divide-and-conquer approach and recursive functions, the algorithm will handle all the details for us. This might be the charm of algorithms, hahaha.
Enough chatter, let's focus on the two key points to solve this problem:
1. Don't think about the whole problem; instead, focus on the local part, looking at just one operator.
We've mentioned this in previous articles, like in Step-by-Step Guide to Binary Trees - Part 1, where we advised focusing on what each node needs to do rather than what the entire tree needs.
In essence, solving recursive algorithm problems is a process of breaking down the whole into parts. You must target a small breakthrough, decompose the problem, and use recursive functions to solve it.
2. Clearly define what the recursive function does, believe in it, and make good use of it.
This is another point we've emphasized before. Since a recursive function calls itself, you must understand what the function does to make correct recursive calls.
Let's delve into how to understand these two key points.
Consider an example where I give you the following expression:
1 + 2 * 3 - 4 * 5
How many ways can you add parentheses to this expression? Please answer in one second.
You probably can't, because parentheses can be nested, and enumerating all possibilities would take effort.
However, while nested parentheses seem daunting to us, algorithms handle them easily with recursion, adding a layer of nesting with each recursive call.
So, as algorithm writers, we just need to think about how many ways we can add parentheses without nesting (i.e., adding only one layer).
Using the same example, we obviously have four ways to add parentheses:
(1) + (2 * 3 - 4 * 5)
(1 + 2) * (3 - 4 * 5)
(1 + 2 * 3) - (4 * 5)
(1 + 2 * 3 - 4) * (5)
Notice the pattern? It's about splitting according to the operators and adding parentheses to the parts on either side of each operator. This is the first key point: focus on each operator, not the whole.
Now, let's look at the third case:
(1 + 2 * 3) - (4 * 5)
Using the minus sign - as a separator, we split the original expression into two: 1 + 2 * 3 and 4 * 5.
Divide and conquer: this step is the 'divide' part, and now we start the 'conquer' part.
1 + 2 * 3 can have two ways to add parentheses:
(1) + (2 * 3) = 7
(1 + 2) * (3) = 9
Or we can write it as:
1 + 2 * 3 = [9, 7]
And 4 * 5 has only one way: 4 * 5 = [20].
Next, can you deduce how many ways (1 + 2 * 3) - (4 * 5) can be parenthesized, or how many different results it can have?
Clearly, (1 + 2 * 3) - (4 * 5) has two results:
9 - 20 = -11
7 - 20 = -13
You might wonder how to get the result 1 + 2 * 3 = [9, 7] using an algorithm.
This is simple. Let's look back at the function signature provided in the problem:
// definition: Calculate all possible operation results of the expression input
List<Integer> diffWaysToCompute(String input);// definition: calculate all possible results of the expression input
vector<int> diffWaysToCompute(string input);# definition: calculate all possible operation results of the expression input
def diffWaysToCompute(input: str) -> List[int]:// definition: Calculate all possible operation results of the expression input
func diffWaysToCompute(input string) []int {}// definition: calculate all possible operation results of the expression input
var diffWaysToCompute = function(input) {
// function body here
};Isn't this function supposed to do exactly that? This is the second key point we mentioned earlier: clearly define the function, believe in it, and use that definition.
You don't need to worry about how the function achieves its goal. Just trust that it can, and use it accordingly. In the end, it will indeed deliver the results.
So, for the example (1 + 2 * 3) - (4 * 5), our calculation logic is essentially this piece of code:
List<Integer> diffWaysToCompute("(1 + 2 * 3) - (4 * 5)") {
List<Integer> res = new LinkedList<>();
// ***** Divide *****
List<Integer> left = diffWaysToCompute("1 + 2 * 3");
List<Integer> right = diffWaysToCompute("4 * 5");
// ***** Conquer *****
for (int a : left)
for (int b : right)
res.add(a - b);
return res;
}vector<int> diffWaysToCompute("1 + 2 * 3 - 4 * 5") {
vector<int> res;
// ****** Divide ******
vector<int> left = diffWaysToCompute("1 + 2 * 3");
vector<int> right = diffWaysToCompute("4 * 5");
// ****** Conquer ******
for (int a : left)
for (int b : right)
res.push_back(a - b);
return res;
}def diffWaysToCompute("(1 + 2 * 3) - (4 * 5)"):
res = []
# ****** divide ******
left = self.diffWaysToCompute("1 + 2 * 3")
right = self.diffWaysToCompute("4 * 5")
# ****** conquer ******
for a in left:
for b in right:
res.append(a - b)
return resfunc diffWaysToCompute("(1 + 2 * 3) - (4 * 5)") []int {
res := []int{}
// ***** Divide *****
left := diffWaysToCompute("1 + 2 * 3")
right := diffWaysToCompute("4 * 5")
// ***** Conquer *****
for _, a := range left {
for _, b := range right {
res = append(res, a - b)
}
}
return res
}var diffWaysToCompute = function("(1 + 2 * 3) - (4 * 5)") {
var res = [];
// *** Divide ***
var left = diffWaysToCompute("1 + 2 * 3");
var right = diffWaysToCompute("4 * 5");
// *** Conquer ***
for (var a of left)
for(var b of right)
res.push(a - b);
return res;
}
diffWaysToCompute("(1 + 2 * 3) - (4 * 5)");Great, now you should fully understand how the example (1 + 2 * 3) - (4 * 5) is calculated. Let's go back to our original problem.
Is the original problem 1 + 2 * 3 - 4 * 5 only the case (1 + 2 * 3) - (4 * 5)? Can it only be split at the minus sign -?
No, each operator can split the original problem into two subproblems. We have already listed all possible ways to split it:
(1) + (2 * 3 - 4 * 5)
(1 + 2) * (3 - 4 * 5)
(1 + 2 * 3) - (4 * 5)
(1 + 2 * 3 - 4) * (5)
So, we need to enumerate each of the above cases. We can further refine the solution code:
class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> res = new LinkedList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
// scan for operators in the expression input
if (c == '-' || c == '*' || c == '+') {
// *** divide ***
// split the string into two parts around the operator and compute them recursively
List<Integer>
left = diffWaysToCompute(input.substring(0, i));
List<Integer>
right = diffWaysToCompute(input.substring(i + 1));
// *** combine ***
// combine the results of the subproblems to form the result of the original problem
for (int a : left)
for (int b : right)
if (c == '+')
res.add(a + b);
else if (c == '-')
res.add(a - b);
else if (c == '*')
res.add(a * b);
}
}
// base case
// if res is empty, it means the expression is a number without any operators
if (res.isEmpty()) {
res.add(Integer.parseInt(input));
}
return res;
}
}class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> res;
for (int i = 0; i < input.size(); i++) {
char c = input[i];
// scan for operators in the expression input
if (c == '-' || c == '*' || c == '+') {
// ******** split ********
// split the string into two parts around the operator and compute them recursively
vector<int> left = diffWaysToCompute(input.substr(0, i));
vector<int> right = diffWaysToCompute(input.substr(i + 1));
// ******** merge ********
// synthesize the result of the original problem through the results of the subproblems
for (int a : left)
for (int b : right)
if (c == '+')
res.push_back(a + b);
else if (c == '-')
res.push_back(a - b);
else if (c == '*')
res.push_back(a * b);
}
}
// base case
// if res is empty, it means the expression is a number without any operators
if (res.empty()) {
res.push_back(stoi(input));
}
return res;
}
};class Solution(object):
def diffWaysToCompute(self, input):
res = []
for i in range(len(input)):
c = input[i]
# scan the operators in the expression input
if c in ['-', '*', '+']:
# ****** divide ******
# split into two strings centered on the operator and recursively compute each part
left = self.diffWaysToCompute(input[:i])
right = self.diffWaysToCompute(input[i+1:])
# ****** conquer ******
# combine the results of subproblems to form the result of the original problem
for a in left:
for b in right:
if c == '+':
res.append(a + b)
elif c == '-':
res.append(a - b)
elif c == '*':
res.append(a * b)
# base case
# if res is empty, it means the expression is a number without any operators
if not res:
res.append(int(input))
return resfunc diffWaysToCompute(input string) []int {
res := []int{}
for i := 0; i < len(input); i++ {
c := input[i]
// scan for operators in the expression input
if c == '-' || c == '*' || c == '+' {
// *** divide ***
// split the expression into two parts around the operator and calculate them recursively
left := diffWaysToCompute(input[:i])
right := diffWaysToCompute(input[i+1:])
// *** conquer ***
// synthesize the result of the original problem through the results of the subproblems
for _, a := range left {
for _, b := range right {
if c == '+' {
res = append(res, a+b)
} else if c == '-' {
res = append(res, a-b)
} else if c == '*' {
res = append(res, a*b)
}
}
}
}
}
// base case
// if res is empty, it means the expression is a number without any operators
if len(res) == 0 {
num, _ := strconv.Atoi(input)
res = append(res, num)
}
return res
}var diffWaysToCompute = function(input) {
let res = [];
for (let i = 0; i < input.length; i++) {
let c = input.charAt(i);
// scan for operators in the expression input
if (c == '-' || c == '*' || c == '+') {
// ***** divide *****
// split the expression at the operator and recursively calculate for both substrings
let left = diffWaysToCompute(input.substring(0, i));
let right = diffWaysToCompute(input.substring(i + 1));
// ***** conquer *****
// combine the results of the subproblems to form the result of the original problem
for (let a of left)
for (let b of right)
if (c == '+')
res.push(a + b);
else if (c == '-')
res.push(a - b);
else if (c == '*')
res.push(a * b);
}
}
// base case
// if res is empty, it means the expression is a number without any operators
if (res.length == 0) {
res.push(parseInt(input));
}
return res;
};With the previous explanation, this code should be easy to understand. It scans the input expression input, splits whenever it encounters an operator, recursively calculates the results, and then merges the results based on the operator.
This is a typical divide-and-conquer approach: first "divide" and then "conquer". First, break down the original problem into multiple subproblems based on the operators, and then synthesize the result of the original problem from the results of the subproblems.
Of course, a key point is in this section of the code:
// base case
// If res is empty, it means the formula is a number without any operators
if (res.isEmpty()) {
res.add(Integer.parseInt(input));
}// base case
// if res is empty, it means the formula is a number without any operators
if (res.empty()) {
res.push_back(stoi(input));
}# base case
# If res is empty, it means the formula is a number, with no operators
def numDistinct(s: str, t: str) -> int:
if not res:
res.append(int(input))// base case
// if res is empty, it means the formula is a number without any operators
if len(res) == 0 {
i, _ := strconv.Atoi(input)
res = append(res, i)
}// base case
// If res is empty, it means the expression is a number without any operators
if (res.length == 0) {
res.push(parseInt(input));
}A recursive function must have a base case to end the recursion. In fact, this part of the code is the base case of our divide-and-conquer algorithm, indicating when you can start "conquering" after "dividing".
We "divide" based on operators. How do we know when to stop? Obviously, when there are no operators left in the expression, we can stop.
Why use res.isEmpty() as the condition? Because when there are no operators in the expression, the if statement won't trigger, and no elements will be added to res.
With this, we have written the solution code for this problem. But what is the time complexity?
If we just look at the code, it's hard to determine the complexity from the number of for loop iterations. So, we need to change our approach. This problem is about finding all possible calculation results, which is essentially like finding all valid bracket combinations for the expression input.
How many valid bracket combinations are there for an expression? This is known as the "Catalan number." The final result is a combination number, and the derivation process is somewhat complex. I won't write it out here, but interested readers can search and learn about it.
Actually, there's a small optimization for this problem: recursive pruning. This can reduce some redundant calculations. For example, consider the following input expression:
1 + 1 + 1 + 1 + 1
According to the algorithm logic, splitting by operators will definitely result in the following two cases:
(1 + 1) + (1 + 1 + 1)
(1 + 1 + 1) + (1 + 1)
The algorithm will recursively process each case, which is essentially redundant calculation. Therefore, we can slightly modify the solution code to add a memo to avoid this repeated calculation:
class Solution {
// memoization
HashMap<String, List<Integer>> memo = new HashMap<>();
public List<Integer> diffWaysToCompute(String input) {
// avoid repeated calculations
if (memo.containsKey(input)) {
return memo.get(input);
}
// ***** nothing changes *****
List<Integer> res = new LinkedList<>();
for (int i = 0; i < input.length(); i++) {
// ...
}
if (res.isEmpty()) {
res.add(Integer.parseInt(input));
}
// ***********************
// add the result to memoization
memo.put(input, res);
return res;
}
}class Solution {
public:
// memoization
unordered_map<string, vector<int>> memo;
vector<int> diffWaysToCompute(string input) {
// avoid repeated computation
if (memo.count(input)) {
return memo[input];
}
// ***** nothing changes *****
vector<int> res;
for (int i = 0; i < input.length(); i++) {
// ...
}
if (res.empty()) {
res.push_back(stoi(input));
}
// ***********************
// add the result to memoization
memo[input] = res;
return res;
}
};class Solution:
# memoization
memo = {}
def diffWaysToCompute(self, input: str) -> List[int]:
# avoid repeated calculations
if input in self.memo:
return self.memo[input]
# ***** nothing changes *****
res = []
for i in range(len(input)):
# ...
if not res:
res.append(int(input))
# ***********************
# *************************
# add the result to memoization
self.memo[input] = res
return res// memoization
var memo = make(map[string][]int)
func diffWaysToCompute(input string) []int {
// avoid repeated computation
if val, ok := memo[input]; ok {
return val
}
// ***** nothing else changes *****
var res []int
for i := 0; i < len(input); i++ {
// ...
}
if len(res) == 0 {
num, _ := strconv.Atoi(input)
res = append(res, num)
}
// ***********************
// add the result to memoization
memo[input] = res
return res
}var Solution = function() {
// memoization
this.memo = {};
};
Solution.prototype.diffWaysToCompute = function(input) {
// avoid repeated calculations
if (this.memo.hasOwnProperty(input)) {
return this.memo[input];
}
// *** nothing changes ***
var res = [];
for (var i = 0; i < input.length; i++) {
// ...
}
if (res.length === 0) {
res.push(parseInt(input));
}
// ***********************
// add the result to memoization
this.memo[input] = res;
return res;
}This optimization does not change the complexity; it simply prunes some special cases, improving the runtime efficiency.