LeetCode 241. Design priorities for operational expressions (divide and conquer / mnemonic recursion / dynamic programming)

---

0 subject

• 241. Design priorities for operation expressions

1 Their thinking

1.1 Divide and conquer + Memory recursion

String by Operator Split into left and right substrings , Calculate the result set of the left and right substrings respectively , Then merge the result set according to the split operator , For substrings, the result set can also be obtained by continuous splitting （ recursive ）

With 2 * 3 - 4 * 5 For example , Split into ：

• 2 and 3 - 4 * 5 Two parts , In the middle is * No. connected
• 2 * 3 and 4 * 5 Two parts , In the middle is - No. connected
• 2 * 3 - 4 and 5 Two parts , In the middle is * No. connected

To prevent double counting , have access to Map To save the result set corresponding to the substring .

1.1.1 Code implementation

class Solution {
    
    //  Memory recursion 
    Map<String, List<Integer>> mem = new HashMap<>();
    public List<Integer> diffWaysToCompute(String expression) {
    
        if (expression.length() == 0) {
    
            return new ArrayList<>();
        }
        //  The current expression has been solved , Go straight back to 
        if (mem.containsKey(expression)) {
    
            return mem.get(expression);
        }
        //  Save the result of the current expression 
        List<Integer> res = new ArrayList<>();

        int num = 0;
        int index = 0;
        //  Consider the case where the expression has only one number 
        while (index < expression.length() && !isOperation(expression.charAt(index))) {
    
            num = num * 10 + (expression.charAt(index) - '0');
            index++;
        }
        if (index == expression.length()) {
    
            res.add(num);
            mem.put(expression, res);
            return res;
        }

        //  Continue splitting the current expression   By operator 
        for (int i = 0; i < expression.length(); i++) {
    
            if (isOperation(expression.charAt(i))) {
    
                List<Integer> resLeft = diffWaysToCompute(expression.substring(0, i));
                List<Integer> resRight = diffWaysToCompute(expression.substring(i + 1));
                //  Combine two result sets by operator 
                for (int j = 0; j < resLeft.size(); j++) {
    
                    for (int k = 0; k < resRight.size(); k++) {
    
                        char operation = expression.charAt(i);
                        res.add(calculate(resLeft.get(j), operation, resRight.get(k)));
                    }
                }
            }
        }
        //  Save to map
        mem.put(expression, res);
        return res;
    }

    private int calculate(int a, char op, int b) {
    
        switch (op) {
    
            case '+' :
                return a + b;
            case '-' :
                return a - b;
            case '*' :
                return a * b;
        }
        return -1;
    }

    private boolean isOperation(char c) {
    
        return !Character.isDigit(c);
    }
}

1.2 Dynamic programming

• Design priorities for operation expressions

2 Reference

• Design priorities for operation expressions
• Detailed analysis of popular ideas , Multiple solutions