Accepted Java Solution


  • 0
    W

    The basic idea is just using DFS and backtracking. I think the question itself is not that HARD, the only tricky part is the tons of edge cases. For example, "000" or Integer.MAX_VALUE.

    Also, I think the example this question listed is not very good because it kind of told us the number will only be single digit. Code is as below

    public List<String> addOperators(String num, int target) {
            List<String> list=new ArrayList<String>();
            if(num.length()==0) return list;
            dfs(num, 0, "", 0, 0, 1, target, list);
            return list;
        }
        public void dfs(String num, int pos, String cStr, int preNum, int cNum, int sign, int target, List<String> list){
            if(sign*cNum+preNum==target && pos==num.length()){
                list.add(cStr);
                return;
            }
            if(pos>=num.length()) return;
            int current=0;
            for(int i=pos;i<num.length();i++){
                 long currentLong=current*10+(long)(num.charAt(i)-'0');
                 if(currentLong>Integer.MAX_VALUE || currentLong<Integer.MIN_VALUE) return;
                 current=(int)currentLong;
                 String currentStr=num.substring(pos, i+1);
                 if(pos==0){
                     dfs(num, i+1, currentStr, preNum+sign*cNum, current,1, target, list); // for the first one, only add
                     if(current==0) break;
                     continue;
                 }
                 dfs(num, i+1, cStr+"+"+currentStr, preNum+sign*cNum, current,1, target, list); // add
                 dfs(num, i+1, cStr+"-"+currentStr, preNum+sign*cNum, current, -1, target, list); // minus
                 dfs(num, i+1, cStr+"*"+currentStr, preNum, current*cNum, sign, target, list); // multiply
                 if(current==0) return;
            }
        }

Log in to reply
 

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