Share my Java backtracking solution


  • 88

    The idea is try to replace every "++" in the current string s to "--" and see if the opponent can win or not, if the opponent cannot win, great, we win!

    For the time complexity, here is what I thought, let's say the length of the input string s is n, there are at most n - 1 ways to replace "++" to "--" (imagine s is all "+++..."), once we replace one "++", there are at most (n - 2) - 1 ways to do the replacement, it's a little bit like solving the N-Queens problem, the time complexity is (n - 1) x (n - 3) x (n - 5) x ..., so it's O(n!!), double factorial.

    That's what I thought, but I could be wrong :)

    public boolean canWin(String s) {
      if (s == null || s.length() < 2) {
        return false;
      }
        
      for (int i = 0; i < s.length() - 1; i++) {
        if (s.startsWith("++", i)) {
          String t = s.substring(0, i) + "--" + s.substring(i + 2);
          
          if (!canWin(t)) {
            return true;
          }
        }
      }
        
      return false;
    }
    

  • 0

    Great explanations!


  • 0
    F
    This post is deleted!

  • 0
    F

    Clean solution, easy to understand!


  • 31

    Great solution! One improvement: adding memorization (HashSet) will greatly reduce time complexity. Although game theory can do much better, I think the following solution is very ideal for an interview. This is a 21ms solution:

    public boolean canWin(String s) {
        if(s == null || s.length() < 2) return false;
           
        Set<String> winSet = new HashSet<String>();
        return canWin(s, winSet);
    }
        
    public boolean canWin(String s, Set<String> winSet){
        if(winSet.contains(s)) return true;
    
        for(int i = 0; i < s.length() - 1; i++) {
            if(s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                   
                String sOpponent = s.substring(0, i) + "--" + s.substring(i + 2);
                if(!canWin(sOpponent, winSet)) {
                    winSet.add(s);
                    return true;
                }
            }
        }
        return false;
    }

  • 3

    s.charAt(i) == '+' && s.charAt(i + 1) == '+' can be shorten as s.startsWith("++", i)


  • 1

    Thanks @jeantimex. I actually tried s.startsWith("++", i) the run time is a bit slower and it's calling a convenient API. Anyway both are fine for an interview.

    I even tried to eliminate substring but it looks like converting to string using new String(charArray) greatly increase the time cost.


  • 2

    Ok, in your solution, you only cache the win set, in my opinion we can also cache the lose set, and we can use a Map <String, Boolean> to help with that.


  • 80

    Thanks to @jeantimex. If we use HashMap to memorize both win string & lose string, we can further reduce time from 208ms to 18ms:

    public boolean canWin(String s) {
        if(s == null || s.length() < 2) return false;
        Map<String, Boolean> map = new HashMap<>();
        return canWin(s, map);
    }
    
    public boolean canWin(String s, Map<String, Boolean> map){
        if(map.containsKey(s)) return map.get(s);
        for(int i = 0; i < s.length() - 1; i++) {
            if(s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                String opponent = s.substring(0, i) + "--" + s.substring(i + 2);
                if(!canWin(opponent, map)) {
                    map.put(s, true);
                    return true;
                }
            }
        }
        map.put(s, false);
        return false;
    }

  • 1

    You are right. We should also cache the lost case. I've posted the Map<String, Boolean> version and the time reduced by 14.3%.


  • 0

    Excellent! :)


  • 0
    Y

    This solution is now "Time Limit Exceeded"...


  • 0
    S

    How can I visually understand this solution? It's hard to imagine.


  • 0
    L

    Could you please analyze the time complexity?


  • 0
    X

    This is really good! Thanks!


  • 1
    5

    I think this solution reduce the complexity from factorial to exponential. With memorization, the complexity depends on how many states the string can be changed to .


  • 0
    R

    Can you please explain, what will be the time complexity of this ?


  • 0
    M

    Could you please explain why canWin() returns true means player 1 is guaranteed to have a winning strategy? Don't we need to check when no move can be made is the current player the player 1 or player 2?


  • -1
    I

    So what if the input is ++++?

    Then say the first player flips the first two, so it becomes --++
    Then the second player flips the next two so it is ----
    SO in this specific recursion path, the function should return that the first player cannot win, right? However, when you recur onto ----, the function will return false, which gets negated into True, which suggests that the first player can win when really he cannot.


  • 0

    Same approach here:

    public class Solution {
        public boolean canWin(String s) {
            if (s == null || s.length() < 2) {
                return false;
            }
            for (String next : generatePossibleNextMoves(s)) {
                if (!canWin(next)) {
                    return true;
                }
            }
            
            return false;
        }
        
        public List<String> generatePossibleNextMoves(String s) {
            List<String> result = new ArrayList<String>();
            if (s == null || s.length() < 2) {
                return result;
            }
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length - 1; i++) {
                if (chars[i] == '+' && chars[i + 1] == '+') {
                    chars[i] = '-';
                    chars[i + 1] = '-';
                    result.add(String.valueOf(chars));
                    chars[i] = '+';
                    chars[i + 1] = '+';
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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