282. Adding operators to expressions: a backtracking problem using the algebraic system

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Topic describes

This is 282 on LeetCode. Adding an operator to an expression is difficult.

Tag: “DFS”, “math”

Given a string num containing only the numbers 0-9 and a target integer target, add the binary operator (not unary) +, -, or * between the digits of num to return any expression that yields the target value.

Example 1:

Input: num = "123", target = 6 output: [" 1 + 2 + 3 ", "1 * 2 * 3"]Copy the code

Example 2:

Input: num = "232", target = 8 output: [" 2 * 3 + 2 ", "2 + 3 * 2]"Copy the code

Example 3:

["1*0+5","10-5"]Copy the code

Example 4:

Input: num = "00", target = 0 output: [" 0 + 0 "and" 0-0 "and" 0 * 0 "]Copy the code

Example 5:

Num = "3456237490", target = 9191Copy the code

Tip:

• 1 <= num.length <= 10
• Num contains only numbers
• 
  $-2^{31} <= target <= 2^{31} – 1$

Backtracking algorithm

The initial idea was to use DFS to find all expressions and then apply (solution) 227. The basic calculator II scheme computes the results of all expressions and adds an expression that evaluates to targettargettarget to the result set.

Given that the length of the original string numnumnum is NNN, there are n− 1n-1n −1 positions that need to be decided because there are four insertion decisions between each position (no insertion sign, +, -, and *). Therefore, the complexity of searching all expressions is O(4n−1)O(4^{n-1})O(4n−1); All expressions need to be computed at the same time, with the complexity O(n)O(n)O(n) O(n∗4n−1)O(n * 4^{n-1})O(n∗4n−1).

The expression length after adding the operator should not exceed 202020, so the total amount of computation should be within 10710^7107, but probably due to constant timeouts (the various optimized double-stack operations are also TLE).

Therefore, we need to consider doing calculations during the search to avoid using227. Basic Calculator IIThis way of calculating the larger constants.

We consider that if we only have + and -, we can easily combine all the expressions of the operation with the backtracking search. However, when * is present, we need to record the multiplication part in the form of a + b * C due to the problem of operation priority.

Prevprevprev (” prevprevprev “); prevprevprev (” prevprevprev “); Discuss the classification of the operation added this time:

• If added this time+Operation, and the
  $k$The value of the item is
  $next$: Then use it directly
  $cur + next$To update the
  $cur$And at the same time
  $next$As the next time
  $prev$;
• If added this time-Operation, and the
  $k$The value of the item is
  $next$: Same, then direct use
  $cur – next$To update the
  $cur$And at the same time
  $-next$As the next time
  $prev$;
• If added this time*Operation, and the
  $k$The value of the item is
  $next$: The priority of the operator needs to be considered
  $next$Is the same as the last operand
  $prev$Perform multiplication, and
  $cur$It’s already adding up
  $prev$So we need to subtract first
  $prev$, plus
  $prev * next$“To update
  $cur$And at the same time
  $prev * next$Also for the next time
  $prev$.

Some details: Note the leading zeros (000 alone as a bit is allowed, but a bit with a head of 000 is not allowed) and the + and – are not unary operators (operators cannot appear at the beginning of expressions).

Code:

class Solution {
    List<String> ans = new ArrayList<>();
    String s;
    int n, t;
    public List<String> addOperators(String num, int target) {
        s = num;
        n = s.length();
        t = target;
        dfs(0.0.0."");
        return ans;
    }
    void dfs(int u, long prev, long cur, String ss) {
        if (u == n) {
            if (cur == t) ans.add(ss);
            return ;
        }
        for (int i = u; i < n; i++) {
            if(i ! = u && s.charAt(u) =='0') break;
            long next = Long.parseLong(s.substring(u, i + 1));
            if (u == 0) {
                dfs(i + 1, next, next, "" + next);
            } else {
                dfs(i + 1,  next, cur + next, ss + "+" + next);
                dfs(i + 1, -next, cur - next, ss + "-" + next);
                long x = prev * next;
                dfs(i + 1, x, cur - prev + x, ss + "*"+ next); }}}}Copy the code

• Time complexity: O(4n)O(4^{n})O(4n)
• Space complexity: O(4n)O(4^{n})O(4n)

conclusion

On the surface, the method only realizes the function of searching and calculating, but in essence, it uses the set of real numbers
$S$And operators+(-Is the essence of+) and*Can form an algebraic system.

Using the algebraic system (S,+,∗)(S, +, *)(S,+,∗), we can ensure that any intermediate result in the operation can be represented by a form such as A + b * C, so we only need to maintain one more suffix string result.

And the algebraic system, and how to determine whether it can be an algebraic system, if you’re interested, you can try to understand it.

The last

This is No.282 of our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some of which have locks, we will first brush all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.