282 Expression Add Operators

282. Expression Add Operators

1. Question

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

Examples:

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

2. Implementation

(1) Backtracking

思路: 这道题主要就是用Backtracking枚举所有可能的结果，但要注意的edge cases和要处理的问题有:

1.以0开头的非个位数,比如01, 012,这些都是invalid的遇到时我们要直接跳过

2.乘法的优先级会高于加减法，比如2+3*4这种情况，我们按顺序2 + 3的话会得到5，但遇到乘号是，我们要减去3，然后用3乘以4得到12再加回2才等到正确的结果14，所以我们在backtracking的过程中，我们要维护prevNum这个变量记录之前的数，以及curRes记录当前的结果，如果遇到乘号时，curRes先减去prevNum,然后再加上prevNum * curNum。

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList();
        StringBuilder expression = new StringBuilder();

        getExpressions(0, num, 0, 0, target, expression, res);
        return res;
    }

    public void getExpressions(int startIndex, String num, long prevNum, long curRes, int target, StringBuilder expression, List<String> res) {
        if (startIndex == num.length() && curRes == target) {
            res.add(expression.toString());
            return;
        }

        int len = expression.length();

        for (int i = startIndex; i < num.length(); i++) {
            if (num.charAt(startIndex) == '0' && i != startIndex) break;

            String curStr = num.substring(startIndex, i + 1);
            Long curNum = Long.parseLong(curStr);

            if (len != 0) {
                getExpressions(i + 1, num, prevNum * curNum, (curRes - prevNum) + (prevNum * curNum), target, expression.append("*").append(curNum), res);
                expression.setLength(len);
                getExpressions(i + 1, num, curNum, curRes + curNum, target, expression.append("+").append(curNum), res);
                expression.setLength(len);
                getExpressions(i + 1, num, -curNum, curRes - curNum, target, expression.append("-").append(curNum), res);
                expression.setLength(len);
            }
            else {
                getExpressions(i + 1, num, curNum, curNum, target, expression.append(curStr), res);
                expression.setLength(len);
            }
        }
    }
}

3. Time & Space Complexity

时间复杂度O(n * 4^(n - 1)), n为num的长度，在num之间有n - 1个slot，对于每个slot我们有4种选择，不插入任何operator，插入3种(+, -, *)operators，对于遍历num的每个位置，我们都要O(4^(n - 1))的时间，总共有n步，所以需要O(n * 4^(n - 1)), 空间复杂度O(n), 递归的深度为n