[Leetcode] 282. Expression Add Operators | 给表达式添加运算符

yPhantom 2020年02月03日 32次浏览

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"] 

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

Input: num = "3456237490", target = 9191
Output: []

这道题是我从494. Target Sum的相似题跳转过来的,本来以为也是一道背包问题,结果是一道组合问题,组合问题当然用backtrack回溯方法来解决了。

回想一下回溯法的几个要点:

  1. 回溯函数的参数要有一个记录结果的list或者数组,这道题中我们设为List<String> res
  2. 有一个记录部分解的参数,这道题中我们设为String path
  3. 用来判断是否满足要求的一些参数以及辅助参数。

那么最后能得到我们的代码了:

class Solution {
    public List<String> addOperators(String num, int target) {
        if (num == null || num.length() == 0) {
            return new ArrayList<>();
        }
        List<String> res = new ArrayList<>();
        backtrack(res, "", num, target, 0, 0, 0);
        return res;
    }
    
    private void backtrack(List<String> res, String path, String num, int target, int start, long eval, long last) {
        if (start == num.length()) {
            if (eval == target) {
                res.add(path);
            }
            return;
        }
        for (int end = start; end < num.length();end++) {
            if (end != start && num.charAt(start) == '0') break;
            String sCur = num.substring(start, end + 1);
            long cur = Long.parseLong(sCur);
            if (start == 0) {
                backtrack(res, sCur, num, target, end + 1, cur, cur);
            } else {
                backtrack(res, path + "+" + sCur, num, target, end + 1, eval + cur, cur);
                backtrack(res, path + "-" + sCur, num, target, end + 1, eval - cur, -cur);
                backtrack(res, path + "*" + sCur, num, target, end + 1, eval - last + last * cur, last * cur);
            }
        }
    }
}

backtrack函数中,start、eval、last都是用来辅助结果判断的。

每一轮递归我们都有一个start和end,用来表示当前递归正在处理的字符串,然后将这个字符串cur加入到部分解path中,同时更新计算值eval,更新记录上一个操作数的遍历last。last主要是为了处理乘法优先级。

比如下面这种情况

it1:    1 + 2
it2:    1 + 2 - 2 + 2 * 3

在每一个递归过程中,开始的start总是固定的,变换的是end,这就保证了解的完备性。

参考链接

Java Standard Backtrace AC Solutoin, short and clear