Leetcode divide and conquer method

241. Design priorities for operation expressions

Given a string containing numbers and operators , Add parentheses to expressions , Change its operation priority to get different results . You need to give the results of all possible combinations . Valid operation symbols include +, - as well as * .

• Divide and conquer thoughts ：

  • Convert bracketed to , For each operation symbol , First execute the mathematical expressions on both sides of the process , Then process this operation symbol .
  • Use recursion to continue to split the left and right expressions of the current traversal symbol .
  • Boundary case , character string No operation symbol , Only numbers .

• example ：5 + 3 * 4 + 2

  • left -> 5
  • right -> 3 * 4 + 2
    • left -> 3
    • right -> 4 + 2
      • left -> 4
      • right -> 2
    • left -> 3 * 4
      • left -> 3
      • right -> 4
    • right -> 2
  • left : 5, right: 3 * (4 + 2) = 18, (3 * 4) + 2 = 14
  • (3 * 4 + 2); (3 * 4) + 2; 3 * (4 + 2); The first two results are the same

class Solution {
    
public:
    vector<int> diffWaysToCompute(string expression) {
    
        int n = expression.length();
        vector<int> ways;
        for (int i = 0; i < n; i++) {
    
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
    
            	//  The left and right sides of the symbol continue to be divided 
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                vector<int> right = diffWaysToCompute(expression.substr(i + 1));
                for (const int& l : left) {
    
                    for (const int& r : right) {
    
                        switch(c) {
    
                            case '+': ways.push_back(l + r); break;
                            case '-': ways.push_back(l - r); break;
                            case '*': ways.push_back(l * r); break;
                        }
                    }
                }
            }
        }
        if (ways.empty()) ways.push_back(stoi(expression)); //  Treatment of boundary conditions 
        return ways;
    }
};

• Memory storage
  • Some partitioned strings may appear multiple times , have access to hash map Store these results , When traversing the string again, directly query the stored results .

class Solution {
    
public:
    unordered_map<string, vector<int>> strMap; //  Create a hash mapping table externally 
    vector<int> diffWaysToCompute(string expression) {
    
        int n = expression.length();
        //  Check whether the result of the expression partition is stored in the hash table 
        if (strMap.count(expression)) {
    
            return strMap[expression];
        }
        vector<int> ways;
        for (int i = 0; i < n; i++) {
    
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
    
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                //  Put the left expression and its corresponding result into the hash mapping table 
                pair<string, vector<int>> instance1(expression.substr(0, i), left);
                strMap.insert(instance1);
                vector<int> right = diffWaysToCompute(expression.substr(i + 1));
                pair<string, vector<int>> instance2(expression.substr(i + 1), right);
                strMap.insert(instance2);
                for (const int& l : left) {
    
                    for (const int& r : right) {
    
                        switch(c) {
    
                            case '+': ways.push_back(l + r); break;
                            case '-': ways.push_back(l - r); break;
                            case '*': ways.push_back(l * r); break;
                        }
                    }
                }
            }
        }
        if (ways.empty()) ways.push_back(stoi(expression));
        return ways;
    }
};

• Dynamic programming ：
  • From the bottom up
  • dp[i][j][] It means the first one i Number to j All possible operation results of numbers
  • j = i -> 0 Direction calculation dp[j][i]; set up i = 3;j = 3,2,1,0; First, we can calculate dp[3][3],dp[2][3],dp[1][3],dp[0][3];dp[2][3] = dp[2][2] * dp[3][3];dp[1][3] = dp[1][1] * dp[2][3]; dp[1][2] * dp[3][3];
  • j = 0 -> i Direction calculation dp[j][i]; set up i = 3;j = 0,1,2,3; Then calculate first dp[0][3], however dp[0][3] = dp[0][0] * dp[1][3];dp[0][1] * dp[2][3]; dp[0][2] * dp[3][3]; Result , If in this order ,dp[2][3] The result of has not been calculated , So you can't get the right result ;

class Solution {
    
public:
    vector<int> diffWaysToCompute(string expression) {
    
        istringstream ss(expression + "+"); //  Add a sign to cut off 
        vector<int> data;
        vector<char> ops;
        int num = 0;
        char op = ' ';
        //  Get the numbers and operation symbols in the expression 
        while (ss >> num && ss >> op) {
    
            data.push_back(num);
            ops.push_back(op);
        }
        int n = data.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>()));
        for (int i = 0; i < n; i++) {
    
            for (int j = i; j >= 0; j--) {
    
                if (i == j) {
    
                    dp[j][i].push_back(data[i]); //  The first  i  The number itself 
                }else {
    
                    for (int k = j; k < i; k += 1) {
     //  since  j  towards  i  Stepping , Consider all the situations 
                    	//  The second one is calculated  j  The number to the first  i  The result of all operations on numbers , Its use  k  Segmentation 
                    	// j  to  i  Can be divided into  j  to  k  And  k + 1  To  i
                        for (const int& left : dp[j][k]) {
    
                            for (const int& right : dp[k + 1][i]) {
    
                                int val = 0;
                                //  With  k  Demarcation , Therefore, call No  k  Operators 
                                switch(ops[k]) {
    
                                    case '+' : val = left + right; break;
                                    case '-' : val = left - right; break;
                                    case '*' : val = left * right; break;
                                }
                                dp[j][i].push_back(val); //  Store results 
                            }
                        }
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
};