241. Design priority for operational expressions: DFS application questions

Title Description

This is a LeetCode Upper 241. Design priorities for operation expressions , The difficulty is secondary .

Tag : 「DFS」、「 Explosive search 」

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 .

The generated test case meets its corresponding output value in line with Bit integer range , The number of different results does not exceed .

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 ：

• expression By numbers and operators '+'、 '-' and '*' form .
• All integer values in the input expression are in the range

DFS

For convenience , We make expression by s.

The data range is , And all the calculation results should be counted , We can use DFS Search all plans .

A given s Only numbers and operators , We can divide the formula into left and right parts according to the operator , Design recursive functions List<Integer> dfs(int l, int r), It means to search the substring All operation results of .

The final answer is dfs(0,n-1), among Is the length of the input parameter string , At the same time, we have an obvious recursive exit ： When given When there are no operators , The search result is The number itself .

Consider how to treat any Calculate ： We can enumerate All operator positions in the range are searched , Suppose the currently enumerated For operator , We can recurse to the left of the operator dfs(l,i-1) Get all the results on the left , To the right of the recursive operator dfs(i+1,r) Get all the results on the right , combination 「 Multiplication principle 」 You can know that with the current operator All schemes of expressions for split points .

It's not hard to find out , All the above processes are made by 「 Small expression 」 The results are derived 「 Large expression 」 Result , So it can also be used 「 Section DP」 Method to solve , Complexity and DFS Agreement .

Code ：

class Solution {
    char[] cs;
    public List<Integer> diffWaysToCompute(String s) {
        cs = s.toCharArray();
        return dfs(0, cs.length - 1);
    }
    List<Integer> dfs(int l, int r) {
        List<Integer> ans = new ArrayList<>();
        for (int i = l; i <= r; i++) {
            if (cs[i] >= '0' && cs[i] <= '9') continue;
            List<Integer> l1 = dfs(l, i - 1), l2 = dfs(i + 1, r);
            for (int a : l1) {
                for (int b : l2) {
                    int cur = 0;
                    if (cs[i] == '+') cur = a + b;
                    else if (cs[i] == '-') cur = a - b;
                    else cur = a * b;
                    ans.add(cur);
                }
            }
        }
        if (ans.isEmpty()) {
            int cur = 0;
            for (int i = l; i <= r; i++) cur = cur * 10 + (cs[i] - '0');
            ans.add(cur);
        }
        return ans;
    }
}

• Time complexity ： The complexity is related to the number of final results , The number of final results is 「 Carter LAN number 」, The complexity is
• Spatial complexity ： The complexity is related to the number of final results , The number of final results is 「 Carter LAN number 」, The complexity is

Last

This is us. 「 Brush through LeetCode」 The first of the series No.241 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases