Monday, July 18, 2016

Expression Add Operators -- Leetcode

Question:
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (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 -> []

Answer:
Method: DFS!
public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<String>();
        Util(res, "", num, 0, target, 0, 0);
        return res;
    }
 
    public void Util(List<String> res, String path, String num, int start, int target, long eval, long lastNum){
        //come to string end!
        if(start == num.length()){
            if(eval == target){
                res.add(path);
            }
        }
     
        for(int i=start;i<num.length();i++){
            if(num.charAt(start)=='0' && i!=start){
                //jump out directly.As no 0xxx number!
                break;
            }
 
            long currNum = Long.parseLong(num.substring(start, i+1));
            //Process the first parsed number!
            if(start == 0){
                Util(res, path + currNum, num, i+1, target, eval + currNum, currNum);
            }else{
                Util(res, path + "+" + currNum, num, i+1, target, eval + currNum, currNum);
                Util(res, path + "-" + currNum, num, i+1, target, eval - currNum, -currNum);
                //Only * used lastNum which comes after last "+/-"!
                Util(res, path + "*" + currNum, num, i+1, target, eval - lastNum + currNum * lastNum, currNum * lastNum);
            }
        }
        return;
    }
}

No comments:

Post a Comment