282. Expression Add Operators

三刷
一直卡着9191的case过不去，发现是减法的时候， prev = -curr
其他的case都可以看二刷的note
 74.51 %
class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        helper(num, target, 0, 0, 0, "", result);
        return result;
    }
 
    private void helper(String num, int target, long eval, long prev, int start, String path, List<String> result) {
        if(start == num.length()) {
            if (eval == target) {
                result.add(path);
            }
            return;
        }
        //[start, end]
        for (int end = start; end < num.length(); end++) {
            if (end != start && num.charAt(start) == '0') {
                break;
            }
            long curr = Long.valueOf(num.substring(start, end + 1));
         
            if (start == 0) {
                helper(num, target, curr, curr, end + 1, path + curr, result);
            } else {
                helper(num, target, eval + curr, curr, end + 1, path + '+' + curr, result);
                helper(num, target, eval - curr, -curr, end + 1, path + '-' + curr, result);
                helper(num, target, eval - prev + prev * curr, prev * curr, end + 1, path + '*' + curr, result);
            }
        }
    }
}



对不同优先级的处理需要存一个PrevValue
特别注意0开头的非零数是Invalid的，需要排除
Time O(3^stringLength)
Space O(1)

二刷

题目不难，难在各种edge case，仔细说一下
一个是0开头的数是invalid的问题，不仅在recursion内部要处理，在第一个character的时候也就是main method里面也要处理

一个是Integer.valueOf()在parse string的时候会有出界的问题
我的解决办法是try catch
别人的写法是用Long


80.08 %

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        if (num == null || num.length() == 0) return result;
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= num.length(); i++) {
            try {
                int firstNum = Integer.valueOf(num.substring(0, i));
                if (firstNum == 0 && i != 1) break;
                sb.append(firstNum);
                helper(num, i, target, firstNum, firstNum, sb, result);
                sb.setLength(0);
            } catch (Exception e) {
                break;
            }
         
        }
        return result;
    }
 
    private void helper(String num, int left, int target, int tempResult, int prevNum, StringBuilder sb, List<String> result) {
     
        // [left, right);
        if (left == num.length()) {
            if (tempResult == target) {
                result.add(sb.toString());
            }
            return;
        }
     
     
        int lastLength = sb.length();
        for (int right = left + 1; right <= num.length(); right++) {
         
            if (num.charAt(left) == '0' && right != left + 1) break;
         
            int currNum = Integer.valueOf(num.substring(left, right));
            // addition
            sb.append("+" + currNum);
            helper(num, right, target, tempResult + currNum, currNum, sb, result);
            sb.setLength(lastLength);
         
            // subtraction
            sb.append("-" + currNum);
            helper(num, right, target, tempResult - currNum, -currNum, sb, result);
            sb.setLength(lastLength);
         
            // multiplication
            sb.append("*" + currNum);
            helper(num, right, target, tempResult - prevNum + prevNum * currNum, prevNum * currNum, sb, result);
            sb.setLength(lastLength);
        }
    }
}

一刷
63.34 %
/*
"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
given a string, a startIndex, a previousSum, a previousValue
for every later digit->iterate through '+', '-', '*'
    new sum = prevSum +/- currNum

*/

public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        if (num == null || num.length() == 0) return result;
        addOperatorsDFSHelper(num, target, 0l, 0l, 0, new StringBuilder(), result);
        return result;
    }
    private void addOperatorsDFSHelper(String num, int target, long prevSum, long prevValue, int startIndex, StringBuilder path, List<String> result) {
        if (prevSum == target && startIndex == num.length()) {
            result.add(path.toString());
            return;
        }
        String currStr;
        long currNum;
        int pathOriginalLength;
        for (int endIndex = startIndex + 1; endIndex <= num.length(); endIndex++) {
         
            currStr = num.substring(startIndex, endIndex);
            if (currStr.startsWith("0") && currStr.length() > 1) continue;
            currNum = Long.parseLong(currStr);
            pathOriginalLength = path.length();
            if (startIndex == 0) {
                path.append(currStr);
                addOperatorsDFSHelper(num, target, prevSum + currNum, currNum, endIndex, path, result);
                path.setLength(pathOriginalLength);
            } else {
                path.append('+' + currStr);
                addOperatorsDFSHelper(num, target, prevSum + currNum, currNum, endIndex, path, result);
                path.setLength(pathOriginalLength);
             
                //'-'
                path.append('-' + currStr);
                addOperatorsDFSHelper(num, target, prevSum - currNum, -currNum, endIndex, path, result);
                path.setLength(pathOriginalLength);
             
                //'*'
                path.append('*' + currStr);
                addOperatorsDFSHelper(num, target, prevSum - prevValue + prevValue * currNum, prevValue * currNum, endIndex, path, result);
                path.setLength(pathOriginalLength);
            }
            //'+'
        }
    }
}