aakarshmadhavan's blog

Add binary operators
By aakarshmadhavan, history, 6 years ago, In English

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.

The trouble here is how to separate the * and the other operators so I can have a "cumulative" sum. Because

1+3*2 is based on 3*2 and not 1+...

Please help me out. Thanks

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Got it using help and skimming over solution

class Solution {
    List<String> sol = new ArrayList<>();
    String s;
    
    public List<String> addOperators(String num, int target) {
        char [] arr = num.toCharArray();
        this.s = num;
        helper(arr, 0, "", 0l, 0l, (long) target);
        return sol;
    }
    
    public void helper(char [] arr, int index, String acc, long prev, long cur, long target){
        if(acc.equals("1+2*3*4")){
            System.out.println(cur);
        }
         if(index >= arr.length){
             if(target == cur){
                 sol.add(acc);
             }
             return;
         }
        
         for(int i = index; i < arr.length; ++i){
             String str = s.substring(index, i + 1);
             if(isInvalidZero(str)) return;
             long curLong = getLong(str);
             
             if(index == 0){
                 helper(arr, i + 1, str, curLong, curLong, target);
             } else {
                 helper(arr, i + 1, acc + '+' + str, curLong, cur + curLong, target);
                 helper(arr, i + 1, acc + '-' + str, -1*curLong, cur - curLong, target);
                 helper(arr, i + 1, acc + '*' + str, prev*curLong, cur - prev + prev*curLong, target);
             }
             
             
         }
    }
    
    public boolean isInvalidZero(String s){
        return (s.isEmpty() || (s.length() > 1 && s.charAt(0) == '0'));
    }
    
    public long getLong(String s){
        return Long.parseLong(s);
    }
}

What an amazing problem. Since I did not get it from this website, how difficult would this be on here?

Div1-C?

→ Reply