Elegant JAVA solution


  • 11
    D
    public class Solution {
    List<String> result =new ArrayList<String>();
    public List<String> addOperators(String num, int target) {
        for(int i=1;i<=num.length();i++){
            if(i>=2 && num.charAt(0)=='0') continue;
            bfs(num.substring(i),num.substring(0,i),target,0,Long.parseLong(num.substring(0,i)),true);
        }
        return result;
    }
    
    public void bfs(String s,String trace,int target,long pre,long current,boolean sign){
        long sum = sign? pre+current:pre-current;
        if(s.length()==0){
            if(sum==(long) target) result.add(trace);
            return;
        }
        for(int i=1;i<=s.length();i++){
            if(i>=2 && s.charAt(0)=='0') continue;
            int number = Integer.parseInt(s.substring(0,i));
            bfs(s.substring(i),trace+"+"+number,target,sum,number,true);
            bfs(s.substring(i),trace+"-"+number,target,sum,number,false);
            bfs(s.substring(i),trace+"*"+number,target,pre,current*number,sign);
        }
    }
    

    }


  • 2
    Y

    I think all the "continue" could be changed to "break"


  • -1
    G

    That's wrong, you can't do a+05, but you can do a+0, so "continue" cannot be replaced with "break".


  • 10
    E

    I believe this is dfs instead of bfs.


  • 1
    Y

    Replacing "continue" with "break" only means stop trying numbers like 051 or any further when you already know 05 is not a valid number. It has nothing to do with 0 because in that case i==1.


Log in to reply
 

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