Java Standard Backtrace AC Solutoin, short and clear


  • 247
    C

    This problem has a lot of edge cases to be considered:

    1. overflow: we use a long type once it is larger than Integer.MAX_VALUE or minimum, we get over it.
    2. 0 sequence: because we can't have numbers with multiple digits started with zero, we have to deal with it too.
    3. a little trick is that we should save the value that is to be multiplied in the next recursion.

    public class Solution {
        public List<String> addOperators(String num, int target) {
            List<String> rst = new ArrayList<String>();
            if(num == null || num.length() == 0) return rst;
            helper(rst, "", num, target, 0, 0, 0);
            return rst;
        }
        public void helper(List<String> rst, String path, String num, int target, int pos, long eval, long multed){
            if(pos == num.length()){
                if(target == eval)
                    rst.add(path);
                return;
            }
            for(int i = pos; i < num.length(); i++){
                if(i != pos && num.charAt(pos) == '0') break;
                long cur = Long.parseLong(num.substring(pos, i + 1));
                if(pos == 0){
                    helper(rst, path + cur, num, target, i + 1, cur, cur);
                }
                else{
                    helper(rst, path + "+" + cur, num, target, i + 1, eval + cur , cur);
                    
                    helper(rst, path + "-" + cur, num, target, i + 1, eval -cur, -cur);
                    
                    helper(rst, path + "*" + cur, num, target, i + 1, eval - multed + multed * cur, multed * cur );
                }
            }
        }
    }

  • 0
    Y
    This post is deleted!

  • 0
    Y

    really nice solution! What i don't understand is why should we avoid overflow, because it is only expression。


  • 0
    C

    good idea, i've modified it : )


  • 1
    C

    because the input is a string so it may be a large number : ) for example if we got 9999999999, the program may want to try 9999999990 + 9,if we use int then it would overflow


  • 1
    S

    Thank you for providing nice solution, I got one testcase can't pass: num = "1921474836681" and target = -2147483648, its expected answer is ["19-2147483668+1"], so maybe we only need to check the final eval is overflowed or not.


  • 1
    C

    Yes, it's a very careful catch, thank you


  • 0
    C
    This post is deleted!

  • 4
    K

    I am really curios to know how did you arrive at the equation of recursive expression for multiplication in the below line ?
    helper(rst, path + "*" + cur, num, target, i + 1, eval - multed + multed * cur, multed * cur );

    I couldn't get this expression and as a result my solution became very lengthy :)


  • 82
    C

    for example, if you have a sequence of 12345 and you have proceeded to 1 + 2 + 3, now your eval is 6 right? If you want to add a * between 3 and 4, you would take 3 as the digit to be multiplied, so you want to take it out from the existing eval. You have 1 + 2 + 3 * 4 and the eval now is (1 + 2 + 3) - 3 + (3 * 4). Hope this could help : )


  • 0
    L

    Exactly the same idea and even the same code :)

    A tiny thing is that when we get cur, I think we should check if(cur > (long)Integer.MAX_VALUE) break; , since the input may cause long overflow when num.substring(pos, i + 1) get longer (the OJ text cases do not contain such case though).


  • 0
    C
    This post is deleted!

  • 0
    C

    Yes, it's a problem while im not sure whether setting Integer.MAX_VALUE as an upper bound is quite proper


  • 0
    L

    yes, I think they should clarify the problem


  • 2
    D

    Very nice solution. Could you pls explain how you handle the merge of two digits like
    '211' -> 22
    Solutions are 2*11 and 21+1. How does your code generate 11 and 21 here? (It does do it but I just cannot figure it out how :) )


  • 0
    Z

    Nice solution, can you tell me what's the time complexity of this solution?


  • 4
    C

    maybe it's O(4^n)


  • 0
    B
    This post is deleted!

  • 0
    B

    I am having hard time understanding about following part.

    eval - multed + multed * cur

    Can you please elaborate on this.


  • 2
    H

    Below statment is very important regarding the speed!

    if(i != pos && num.charAt(pos) == '0') break;
    

    I did some tests. If I use my below code to handle 0s case, then the running time will be 100ms slower!

    long right1 = Long.valueOf(right.substring(0, i));
    if(!(right1 + "").equals(right.substring(0, i))) continue;

Log in to reply
 

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