Massive Algorithms: LeetCode 294

LeetCode 294 - Flip Game II

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

Example:

Input: s = "++++"
Output: true 
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm's runtime complexity

X. DFS + Cache
https://discuss.leetcode.com/topic/27250/share-my-java-backtracking-solution/10
https://discuss.leetcode.com/topic/27351/java-backtracking-solution-with-time-optimization-through-dp-205ms-19ms
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;
}

https://discuss.leetcode.com/topic/34617/simple-java-solution-with-time-complexity-analysis-exponential-vs-factorial

T(N): total ways to flip the string of length N. Assume the original string is "+++++++++". Move the "--" from left to write you will get: "--+++++++" (T(N - 2)), "+--++++++" (T(N - 3)), "++--+++++"(T(2) * T(N - 4)), "+++--++++"(T(3) * T(N - 5)), .......,"++++++--+"(T(N - 3)), "+++++++--" T(N - 2)

When a string separated by "--", e.g., "+++--++++", the time complexity is T(3) * T(N - 5), not T(N - 2). Note, T(3)*T(N - 5) < T(N - 2). So, the correct equation should be (we need to test every flip strategy)

T(N) = T(N-2) + T(N-3) + (T(2) * T(N-4)) + (T(3) * T(N-5)) + ... (T(N-5) * T(3)) + (T(N-4) * T(2)) + T(N-3) + T(N-2)

        public boolean canWin(String s) {
            char[] list = s.toCharArray();
            return helper(list);
        }
        
        private boolean helper(char[] list) {
            for (int i = 0; i < list.length - 1; i++) {
                if (list[i] == '-' || list[i + 1] == '-') continue;
                list[i] = '-';
                list[i + 1] = '-';
                
                boolean otherWin = helper(list);
                //need to go back to the original state before return
                list[i] = '+';
                list[i + 1] = '+';
                
                if (!otherWin) return true;
            }
            
            return false;
        }

https://leetcode.com/discuss/64350/short-java-%26-ruby?show=64350#q64350
You win if and only if you can make some move so that the resulting state can't be won. One thing I do differently from everyone else so far is that I replace "++" with "-" instead of "--".
public boolean canWin(String s) { for (int i=-1; (i = s.indexOf("++", i+1)) >= 0; ) if (!canWin(s.substring(0, i) + "-" + s.substring(i+2))) return true; return false; }

Both the library-searching and the "-"-replacement seem to speed it up significantly, here are results of submitting different similar solutions five times each:

Average 153 ms: Mine with "-" (150, 156, 152, 149 and 156)
Average 169 ms: Mine with "--" (184, 169, 156, 162 and 174)
Average 209 ms: easonhu's (214, 204, 207, 207 and 213)
Average 221 ms: jeantimex's (168, 196, 202, 194 and 345) (without the 345 the average is 190 ms)

Stefan, you can really speed it up by avoiding building string objects. The usage of chars[] for the backtracking can go down to 27ms. Try this one:

public boolean canWin(String s) {
    if (s == null) return false;    
    return canWin(s.toCharArray());
}
private boolean canWin(char[] chars) {
   for (int i = 0; i < chars.length - 1; i++) {
        if (chars[i] == '+' && chars[i+1] == '+') {
            chars[i] = chars[i+1] = '-';
            boolean win = !canWin(chars);
            chars[i] = chars[i+1] = '+'; //backtrack.
            if (win)
                return true;
        }
    }
    return false;
}

Using StringBuilder
http://www.chenguanghe.com/flip-game-ii/
这个backtracking很好想, 就是假设call这个function的人是先手, 然后尝试所有的翻转, 如果不能翻就说明先手的人不能保证必胜.

public boolean canWin(String s) {

    for (int i = 0; i < s.length() - 1; ++i)

        if (s.charAt(i) == '+' && s.charAt(i + 1) == '+' && !canWin(s.substring(0, i) + "--" + s.substring(i + 2)))

                return true;

    return false;

}

http://www.meetqun.com/thread-11570-1-1.html

public class Solution {
public boolean canWin(String s) {
int n = s.length();
if(n<=1) return false;
return dfs(s);
}
private boolean dfs(String s){
StringBuffer buffer = new StringBuffer();
buffer.append(s);
for(int i=0;i<s.length()-1;i++){
if(s.charAt(i)==s.charAt(i+1)&&s.charAt(i+1)=='+'){
buffer.setCharAt(i,'-');
buffer.setCharAt(i+1,'-');
if(!dfs(buffer.toString())) return true;
buffer.setCharAt(i,'+');
buffer.setCharAt(i+1,'+');
}
}+ t# Z, W) W$ ~, {, v
return false;1 m+ M3 o5 S$ v9 s0 T. z) p" N
}; k; {. Q8 Q7 w Q; e$ x, h
}

对每次回溯都检查是否有走下一步的可能，如果没有可能有下一步，意味着肯定是输的，所以返回false。如果有下一步，检查对手在下一步的基础上是否保证会赢，如果对手在下一步基础上保证会赢，则继续寻找其他走法；如果对手在下一步不能保证会赢，意味着如果我们走该次走法，可以在以后的比赛中通过某种走法保证对手输，返回true。如果发现无论怎么走对手都会赢，也返回false。
这样的代码复杂度是O（n！），如果输入是一个长度为N的"+++++...+++"，T(N)=T(N-2)+T(N-3)+(T(2)+T(N-4))+(T(3)+T(N-5))+....+(T(N-5)+T(3))+(T(N-4)+T(2))+T(N-3)+T(N-2) = 2(T(2)+T(3) +..T(N-2))<N*T(N-2) = N(N-2)(N-4)..3*2 < n!

let's check the time complexity: Suppose originally the board of size N contains only '+' signs, then roughly we have:

T(N) = T(N-2) + T(N-3) + [T(2) + T(N-4)] + [T(3) + T(N-5)] + ... 
        [T(N-5) + T(3)] + [T(N-4) + T(2)] + T(N-3) + T(N-2)
     = 2 * sum(T[i])  (i = 3..N-2)

You will find that T(N) = 2^(N-1) satisfies the above equation. Therefore, this algorithm is at least exponential.

X. Use a HashMap to avoid duplicate computation

The idea of the solution is clear, but the time complexity of the backtracking method is high. During the process of searching, we could encounter duplicate computation as the following simple case.

One search path:

Input s = "++++++++"

Player 0: "--++++++"

Player 1: "----++++"

Player 0: "----+--+"

Player0 can win for the input string as "----++++".

Another search path:

Player 0: "++--++++"

Player 1: "----++++"

Player 0: "----+--+"

(Duplicate computation happens. We have already known anyone can win for the

input string as "----++++".)

public boolean canWin(String s) { if (s == null || s.length() < 2) { return false; } HashMap<String, Boolean> winMap = new HashMap<String, Boolean>(); return helper(s, winMap); } public boolean helper(String s, HashMap<String, Boolean> winMap) { if (winMap.containsKey(s)) { return winMap.get(s); } for (int i = 0; i < s.length() - 1; i++) { if (s.startsWith("++", i)) { String t = s.substring(0, i) + "--" + s.substring(i+2); if (!helper(t, winMap)) { winMap.put(s, true); return true; } } } winMap.put(s, false); return false; }
https://leetcode.com/discuss/64291/share-my-java-backtracking-solution

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.

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.

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%.

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.

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; }

https://leetcode.com/discuss/64522/simple-backtracking-inspired-by-flip-game-i

public boolean canWin(String s) { for (String next : generatePossibleNextMoves(s)) if(!canWin(next)) return true; return false; }

public boolean canWin(String s) { List<String> list = new ArrayList<>(); for(int i = 0; i < s.length() - 1; i++){ if(s.charAt(i) == '+' && s.charAt(i + 1) == '+') list.add(s.substring(0, i) + "--" + s.substring(i + 2, s.length())); // generate all possible sequence after every attempt } for(String str : list){ if(!canWin(str)) // if there is any one way the next player can't win, take it and you'll win return true; } return false; }

X.
https://discuss.leetcode.com/topic/27282/theory-matters-from-backtracking-128ms-to-dp-0ms
If you are interested to learn more, this post shares a more sophisticated solution using game theory (it reduces the running time to 0 seconds!).

Now let's check the time complexity: Suppose originally the board of size N contains only '+' signs, then roughly we have:

T(N) = T(N-2) + T(N-3) + [T(2) + T(N-4)] + [T(3) + T(N-5)] + ... 
        [T(N-5) + T(3)] + [T(N-4) + T(2)] + T(N-3) + T(N-2)
     = 2 * sum(T[i])  (i = 3..N-2)

You will find that T(N) = 2^(N-1) satisfies the above equation. Therefore, this algorithm is at least exponential.

Concept 1 (Impartial Game): Given a particular arrangement of the game board, if either player have exactly the same set of moves should he move first, and both players have exactly the same winning condition, then this game is called impartial game. For example, chess is not impartial because the players can control only their own pieces, and the +- flip game, on the other hand, is impartial.

Concept 2 (Normal Play vs Misere Play): If the winning condition of the game is that theopponent has no valid moves, then this game is said to follow the normal play convention; if, alternatively, the winning condition is that the player himself has no valid moves, then the game is a Misere game. Our +- flip has apprently normal play.

Now we understand the the flip game is an impartial game under normal play. Luckily, this type of game has been extensively studied. Note that our following discussion only applies to normal impartial games.

Sprague-Grundy theory

X. Brute force
https://discuss.leetcode.com/topic/27250/share-my-java-backtracking-solution
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.

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;
}

TODO:
http://www.1point3acres.com/bbs/thread-144510-1-1.html

Read full article from [LeetCode] Flip Game II - jcliBlogger - 博客园

LeetCode 294 - Flip Game II

Labels

Popular Posts