Why my solution cannot pass "123456789", "45"


  • 0
    W

    public static List<String> addOperators(String num, int target) {
    List<String> res = new ArrayList<String>();

        for(int i = 1; i<= num.length(); i++){
            long leftSide = Long.valueOf(num.substring(0,i));
            String subRes = "" + (int)leftSide;
            dfs(res, num, target, i, subRes, leftSide, leftSide, '#');
        }
       
        return res;
    }
    
    public static void dfs(List<String> res, String num, int target, int index, String subRes, long currentValue, long preLeft, char sign){
        if(index == num.length() && (int)currentValue == target){
            res.add(subRes);
            return;
        }
            for(int i = index + 1; i <= num.length(); i ++){
                long rightValue = Long.valueOf(num.substring(index, i));
                dfs(res, num, target, i, subRes + "+" +  rightValue, currentValue + rightValue, rightValue, '+');
                dfs(res, num, target, i, subRes + "-" +  rightValue, currentValue - rightValue, rightValue, '-');
                long newLeft;
                if(sign == '-'){
                    newLeft = currentValue + preLeft - preLeft * rightValue;
                }else if(sign == '+'){
                     newLeft = currentValue - preLeft + preLeft * rightValue;
                }else {
                    newLeft = currentValue * rightValue;
                }
                dfs(res, num, target, i, subRes + "*" +  rightValue, newLeft, newLeft, sign);
            }
        
    }

  • 1
    D

    Your solution is wrong. Let's consider the expression "1+2-34*5*6-7*89" when your algorithm evaluates it. Let 's use Dry Run Table to trace your algorithm.
    Start with string "123456789", and the target 45. Your dfs call will be:

    currentValue  preleft  sign  |  rightValue  subRes            newLeft
    1               1       #    |  2           1                  
    1+2 = 3         2       +    |  34          1+2
    3-34 = -31      34      -    |  5           1+2-34            -31+34-34*5=-167
    -167            -167    -    |  6           1+2-34*5          -167-167+167*6=668
    668             668     -    |  7           1+2-34*5*6
    668-7=661       7       -    |  89          1+2-34*5*6-7      661+7-7*89=45
    45              45      -    |  _           1+2-34*5*6-7*89
    

    Your dfs yields the final result is 45, which is wrong because 1+2-34*5*6-7*89=-1640.
    You can check other solutions in the discussion threads to correct your solution ^_^


  • 0
    R

    @wwwlinying said in Why my solution cannot pass "123456789", "45":

    dfs(res, num, target, i, subRes + "*" + rightValue, newLeft, newLeft, sign);

    should be dfs(res, num, target, i, subRes + "*" + rightValue, newLeft, preLeft * rightValue, sign);


Log in to reply
 

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