LeetCode 0241. Design priority for arithmetic expressions - DFS

【LetMeFly】241. Design priorities for operation expressions

Force button topic link ：https://leetcode.cn/problems/different-ways-to-add-parentheses/

Give you a string of numbers and operators  expression , Combine numbers and operators according to different priorities , Calculate and return the results of all possible combinations . You can In any order Return to the answer .

 

Example 1：

 Input ：expression = "2-1-1"
 Output ：[0,2]
 explain ：
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2：

 Input ：expression = "2*3-4*5"
 Output ：[-34,-14,-10,-10,10]
 explain ：
(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

 

Tips ：

• 1 <= expression.length <= 20
• expression By numbers and operators '+'、'-' and '*' form .
• All integer values in the input expression are in the range [0, 99] 

Method 1 ：DFS

This problem makes it easy to think of recursion .

We use the function dfs(string s, int l, int r) To compute strings s Of [l, r) What value can a part represent .

vector<int> dfs(string& s, int l, int r) {
      // [l, r)
    vector<int> ans;

    // Code here

    return ans;
}

So we just need to call dfs(s, 0, s.size()) that will do .

vector<int> diffWaysToCompute(string& expression) {
    
    return dfs(expression, 0, expression.size());
}

So the next question is dfs How to write a function .

It's not hard .

• If the string s Of [l, r) If there is no operator in , Recursion ends , We just need to return a unique value .( for example 125)

  if (!hasOp) {
          //  There is no operator 
      ans.push_back(atoi(s.substr(l, r - l).c_str()));
  }
  

• otherwise , We take all operators as the boundary , Find all possible values on the left side of the operator respectively 、 All possible values on the right , Then do operations one by one , You get a new value .

  if (s[i] == '+' || s[i] == '-' || s[i] == '*') {
        
      hasOp = true;
      vector<int> left = dfs(s, l, i);
      vector<int> right = dfs(s, i + 1, r);
          for (auto& a : left)
              for (auto& b : right)
                  ans.push_back(a OP b);  //  among OP by +、- or *
  }
  

meanwhile , We use hash tables map Record the calculated value .

map<pair<int, int>, vector<int>> ma;

vector<int> dfs(string& s, int l, int r) {
    
    if (ma.count({
    l ,r}))  //  Calculated [l, r) You don't need to calculate it again 
        return ma[{
    l, r}];
    
    // Code Here

    return ma[{
    l, r}] = ans;  //  This is the first calculation , Before returning the result, use the incidentally hash table to record , Avoid double counting next time 
}

• Time complexity $O(2^n)$, among $n$ Is the number of operators contained in the original string
• Spatial complexity $O(2^n)$

The specific complexity will not be proved here , But I'm sure I can .

AC Code

C++

class Solution {
    
private:
    map<pair<int, int>, vector<int>> ma;

    vector<int> dfs(string& s, int l, int r) {
      // [l, r)
        if (ma.count({
    l ,r}))
            return ma[{
    l, r}];
        vector<int> ans;
        bool hasOp = false;
        for (int i = l; i < r; i++) {
    
            if (s[i] == '+' || s[i] == '-' || s[i] == '*') {
    
                hasOp = true;
                vector<int> left = dfs(s, l, i);
                vector<int> right = dfs(s, i + 1, r);
                if (s[i] == '+')
                    for (auto& a : left)
                        for (auto& b : right)
                            ans.push_back(a + b);
                else if (s[i] == '-')
                    for (auto& a : left)
                        for (auto& b : right)
                            ans.push_back(a - b);
                else if (s[i] == '*')
                    for (auto& a : left)
                        for (auto& b : right)
                            ans.push_back(a * b);
            }
        }
        if (!hasOp) {
    
            ans.push_back(atoi(s.substr(l, r - l).c_str()));
        }
        return ma[{
    l, r}] = ans;
    }
public:
    vector<int> diffWaysToCompute(string& expression) {
    
        return dfs(expression, 0, expression.size());
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125555659