14 line java solution


  • 0
    B
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<String>();
        if(num.length() == 0) return res;
        DFS(num, 0, 1, Long.parseLong("" + num.charAt(0)), 1, res, target, "" + num.charAt(0));
        return res;
    }
        
    public void DFS(String s, long dump, long mult, long concat, int idx, List<String> res, long target, String expr){
        if(dump + mult*concat > Integer.MAX_VALUE || dump + mult*concat < Integer.MIN_VALUE) return;
        if(idx == s.length()){
            if(dump + mult*concat == target) res.add(expr);
        } else {
            long curDigit = Long.parseLong("" + s.charAt(idx));
            DFS(s, dump + mult*concat, 1, curDigit, idx+1, res, target, expr + "+" + s.charAt(idx));
            DFS(s, dump + mult*concat, -1, curDigit, idx+1, res, target, expr + "-" + s.charAt(idx));
            DFS(s, dump, mult*concat, curDigit, idx+1, res, target, expr + "*" + s.charAt(idx));
            if(concat != 0) DFS(s, dump, mult, concat*10+curDigit, idx+1, res, target, expr + s.charAt(idx));
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.