FlipGameII [source code]

public class FlipGameII {
static
/******************************************************************************/
public class Solution {
    Map<String, Boolean> memo = new HashMap<>();

    public boolean canWin(String s) {
        if (s == null || s.length() < 2)
            return false;
        if (memo.containsKey(s))
            return memo.get(s);
        boolean res = false;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.startsWith("++", i)) {
                String next = s.substring(0, i) + "--" + s.substring(i + 2);
                if (!canWin(next)) {
                    res = true;
                    break;
                }
            }
        }
        memo.put(s, res);
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FlipGameII.Solution tester = new FlipGameII.Solution();
        String[] inputs = {
            "++++", "true",
            "++++++", "true",
            "+++++", "false",
            "++++-++++++", "true",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String s = inputs[2 * i];
            boolean ans = inputs[1 + 2 * i].equals("true");
            System.out.println(Printer.separator());
            boolean output = tester.canWin(s);
            System.out.println(
                Printer.wrapColor(s, "magenta") +
                " -> " + output +
                Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
                );
        }
    }
}

这个题目本身拿到还是没有思路的, 第一个想法是用DP来做, 但是想了一下, 这个题目到底哪里DP了呢?

另外还是一个没有解决的问题, 到底一个问题, 什么样的特点才会激发你去向DP这个方向来想呢? 比如这个问题, 实际上往DP这个方向去想是合理的, 因为这个题目有大量位置和顺序都未知的uncertainty. 但是这个问题也不符合我们之前的最值搜索问题的定义啊? 所以之前那个框架定义其实是不够完整的; 这里即使就是一个单纯的return boolean的问题, 照样可以联想到DP; 另一个方面来说, 最值搜索问题可以理解为search problem, 而这里这个问题可以理解为一个decision problem; 而以前学算法的时候学过, 这两种问题其实是可以互相转换的;

所以对于所有的decision或者search problem, 我们都可以有这样一个mental node:

• deterministic solution: 这种往往是读完题目之后, 能够快速理解题目本身的意思, 想到一个解法的题目. 同样, greedy应该属于这个范畴;
• DFS. DFS其实就是最简单的穷搜; DFS本身还有两种优化:
  • backtracking;
  • DP;
    • pruning. 严格来说这个不能跟backtracking和DP放在一个类别, 因为那两个其实代表的是全新的两个approach了; 而pruning则是一个可以适用于所有的DFS的一个优化; 另外, 以前我认为memoization也是一个可以适用到所有的DFS上面的优化, 不过后来想想还是不对头;

这样说好像还算合理, 所以其实只是我以前少思考了一个level而已, 而不是对这个node的fanning本身的理解有问题; 另外, 地里看面经的时候, 发现很多人真正临场面试的时候, DFS用的相当多, 所以其实DFS就是一个fallback, 就是一个穷搜的救命稻草;

另外这个问题的tag提示是backtracking问题, 想了一下, 好像可以做;

另外这个问题让人联想到之前的NimGame这个题目, 跟这个问题类似的一个地方是, 两个问题都属于两个玩家队阵的一个game, 而且都是一个只要输出胜负关系的game; 当时Nim这个题目的时候, 我们的一个做法是判断只要对方输, 那么我们就赢, 这种思考逻辑其实是一个类似DP的思考逻辑, 在那个问题的context里面, 是合理的; 但是这里我们这个做的不是DP, 而是一个backtracking, 所以单纯的你输我就赢的思路并不适用;

首先还是思考一下, 你的recursive return value代表的是什么: 每一个level, 每一个subproblem, 你拿到的就是一个subproblem对应的instance, 你return什么? 你能return的其实只有is there any possible flip left. 而不是直接就能return胜负关系; 那么你这个recursive return value最后怎么转换到胜负关系这个上面, which is our desired target value? 这里我能想到的方法只有flag了, 对每一个subproblem给一个参数作为flag/tag, 然后当出现no possible flip(也就是return FALSE)的时候, 我们直接通过tag来判断当前是谁的turn, 然后得到当前这条path对应的一系列操作, 最后是谁胜.

这里还有一个问题, 我们题目的desired到底是什么? 仔细看题目, 是要你guarantee第一个人胜利; 这个就是一个比较严格的要求了, 你必须把整个search tree都走完, 才能知道是否能够guarantee win; 不对, 好像可以prune? 只要有一条path发现是对方win, 那么我们就直接可以结束了? 这个想法本身是对的, 但是好像不知道具体这个premature exit怎么实现? 想了半天, 只能做一个global flag, 然后每一个iteration开始之前check flag, 如果flag表示已经结束搜索(can't guarantee win for first player), 那么直接就return;

另外这里分析半天其实都是按照DFS的思路在分析, 但是好像这一题我们要做的应该是backtracking? backtracking的一个重要特点就是有一个undo when exit的操作; 这个还正好就是这一题可以实现的地方; 另外, 这里subproblem是通过start index来定义的, 一定程度上这个也可以类比于backtracking问题当中的那个flag array; 另外, 设计helper的参数表的时候, 因为有一个是index, 设计的时候要想好, 这个index是不是inclusive的(虽然一般start index都是inclusive的, 不过如果碰到end index, 那么就要小心了). 虽然无论是否inclusive, 最后一般都能把算法写出来, 但是两种不同的思路最后对代码的写法有影响, 尤其是end index是否index对于mid这种东西的计算有比较大的影响;

另外关于这里这个helper的设计, 我想了一下, 好像用Side Effect的思路更好? 你思考一下整个search tree; 在中间的internal node, 我们其实是得不到任何的信息的. 真正能够得到有用信息的, 就是在几个leaf位置, 要么给出的是win, 要么是lose; 我们最后要得到的结果是guarantee, 所以就是没有任何一个leaf是loose; 这个首先, 肯定是有pruning发挥的空间的, 明显的类似short circuit的情形; 另外我们这里为什么需要这个return value? 这个return value在internal node之间是没有任何必要的. 在internal的一个node, 是根本不关心下面一个node是否can still flip something的, 除非是can not, which means the next node is a leaf. But if it's not a leaf, then I don't care that he still has something left to flip in the next move;

当然你可以说, 我们在leaf的时候可以返回一个I win or I lose的信息, 然后每一个leaf的全都上行返回给root, 最后在root处判断, 这样返回值还是有意义, 但是这样就有一个问题, 必须走完整个tree, 这种依赖返回值的判断思路, 是无法实现premature exit的;

另外上面说的这个global, 当然我们一般的做法是用instance var或者用accum; 这一题好像用accum不好做, 因为boolean是一个primitive; 所以干脆就用instance var了;

仔细看了一下题目, 我好像对这里这个guarantee理解的不太对; 比如的例子的这个++++, 如果你flip的是1,2, 那么最后肯定是win, 但是如果你flip的是0,1, 那么你就是lose; 这种情况下, 题目认为还是可以算作是guarantee的; 所以这里最后要求的到底是什么意思?

想了一下, 好像是exist一个first move, 这个move走完之后, 一定win; 所以我们只要对所有的first move分别进行DFS, 这一个第一个level, 只要有一个win就行; 但是每一个第一个level的node对应的subtree, 要求全win;

另外, 我这个subproblem用start进行划分的方法不对, 因为比如你在某一个i进行了flip之后, 你下一个start选择的是i+2, 这个是有问题的, 因为下一手是可以在当前这个i的前面继续flip的; 所以我感觉还是必须用undo的思路, 把整个array都不停的传递; 另外, 这样定义subproblem之后, 每一个subproblem你拿到的只有这么一个被变形过的string作为你的instance, 你怎么判断base case? 这个值得思考一下;

一个小问题, 我前面认为有返回值的话, 没有办法做premature exit. 实际上应该还是可以的; 比如假如我们sensitive的是FALSE, 那么我们每一个level做一个buffer, 每一个iteration一个recursive call, 每一个recursive call的结构都&&到这个buffer里面去, 然后每一个iteration开头的时候判断这个buffer: 如果是FALSE就直接停止; 这个是能达到跟使用global一样的效果的;

事实上, 这个做法是比global, 或者说void helper的做法好的! 因为这个做法可以实现memo. 如果你直接用void的做法来做, 最后的memo几乎是没有办法实现的; 不过这种void的recursion改成一个有返回值的其实也不用担心, 改起来也很好改: 最后一个return直接就是类似return result of recursive call的格式就行了, 也就是触底之后直接只在leaf获得结果, 并且这个结果直接就向上无修改的传递就行了; 当然了, 因为这里的fanning大于1, 所以无修改肯定是不行的, 要用一些逻辑组合, 但是大概意思你应该懂了;

后来发现我对这个题目"guarantee a win"的理解还是不正确. 后面查看了一下discussion最优解的写法, 好像其实问的就是exists a win的意思;

这个是我一开始自己写的一个算法:

public class Solution {  
    boolean mustWin = true;  

    public boolean canWin(String s) {  
        char[] chs = s.toCharArray();  
        for (int i = 0; i < chs.length - 1; i++) {  
            if (chs[i] == '+' && chs[i + 1] == '+') {  
                mustWin = true;  
                chs[i] = '-';  
                chs[i + 1] = '-';  
                flip(chs, false);  
                if (mustWin)  
                    return true;  
                chs[i] = '+';  
                chs[i + 1] = '+';  
            }  
        }  
        return false;  
    }  

    public void flip(char[] chs, boolean isMyTurn) {  
        System.out.println(Printer.array(chs) + " > " + (isMyTurn ? "me" : "you"));  
        if (!mustWin)  
            return;  
        boolean flipped = false;  
        for (int i = 0; i < chs.length - 1; i++) {  
            if (chs[i] == '+' && chs[i + 1] == '+' && mustWin) {  
                flipped = true;  
                chs[i] = '-';  
                chs[i + 1] = '-';  
                flip(chs, !isMyTurn);  
                chs[i] = '+';  
                chs[i + 1] = '+';  
            }  
        }  
        if (!flipped) {  
            if (isMyTurn) {  
                mustWin = false;  
            }  
            System.out.println(Printer.array(chs) + " > " + Printer.wrapColor(mustWin + "", "magenta"));  
        }  
    }  
}

这个算法判断的是, there exists a flip for player1, so that after he takes this move, the game is guaranteed to be his. 但是这个显然不是题目问的意思; 题目问的其实就是是否至少有一种赢法. 这个就比较好做了;

另外这题其实用char array的方法不好, 因为后面还要做memo; 你如果用char array, 后面要不停的在string之间转换, 这个就很麻烦了; 所以这题其实还是直接用string做比较好, 有点像舍不得孩子套不着狼的意思;

另外, 使用immutable的string也有一个好处, 就是不用专门去undo; 因为根本就没有mutation/change发生;

简单算法还是很好写的, 下面就是加一个memo, 这个也是因为用string才得以可行;

最后的速度是25ms (64%), 还可以接受;

另外这个问题, 跟NimGame那一题一起看, 可以看到体现了一个共同的特点: 就是在这种两人对着下棋类的游戏问题里面, 经常的做法就是这种类似DP的思路: 我是否win, 取决于对手是否lose; recursion的每一个iteration就是相当于是一张全新的棋谱, 你不用考虑当前是谁的turn, 只要你保证最后的返回值有一个正反交替的过程(他输我就赢), 那么最后的结果跟你自己直接在参数表里加一个tag是一样的; 但是采用返回值的正反交替而不是tag的正反交替有一个好处: memo更好写. 你如果参数表超过一个参数, 那么最后memo就会很难设计了;

当然, 只是假设, 假设我们这个game是一个多玩家循环玩的game, 那么在参数表里面加一个用来表示whose turn的tag感觉还是有必要的;

另外, 更重要的一点是这种下棋类的题目, 很多时候一个对每一个subproblem, 其实思考的就是只有第一步; 你拿到一个subproblem, 然后你思考你自己当前这一步怎么走就行了, 然后对于下一步, 直接看对手的反馈就行了; 而下一步对于对手而言, 他其实思考的也只是他当前的这个"第一步";

另外, 关于这个substring. substring(int, int)这个我们是熟悉的, 第一个是inclusive的起点, 第二是exclusive的end; 但是substring(int)呢? 这个参数是inclusive的start这个我们是知道的, 但是实际上, 这个参数可以多取一个值, 就是length:

java> String s = "abcde"  
java.lang.String s = "abcde"  
java> s.substring(s.length())  
java.lang.String res1 = ""  
java> int l = s.length()  
int l = 5  
java> s.substring(l - 1)  
java.lang.String res3 = "e"  
java> s.substring(l )  
java.lang.String res4 = ""  
java> s.substring(l+1 )  
java.lang.StringIndexOutOfBoundsException: String index out of range: -1  
java> s.substring(0, l)  
java.lang.String res5 = "abcde"  
java> s.substring(0, l+1)  
java.lang.StringIndexOutOfBoundsException: String index out of range: 6

另外如果还是不能理解这个算法和这个题目的意思, 可以用Bottom-Up的方式来思考: 这里的一个base case, 比如说是-----(注意这里主体逻辑是一个premature exit的, 其实是一个lor chain的操作). 那么它的上一层, --++-, 是TRUE; 为什么呢, 因为在--++-这个位置, 只要一个flip之后, 就得到-----, which is false, 而这一个FALSE就足以让我们认为--++-是TRUE, 所以这个意思也很明显了; 只要我们有一个move可以让对方形成死棋, 那么我们就是TRUE; 关键就是怎么理解这个TRUE的含义(类似之前学习逻辑proposition的时候, 更多的时候就是理解TRUE背后对应的是什么fact); as long as there exists one move so that the opponent is false, we are true. 所以这个TRUE的含义很明显了, 就是我们可以win, 而不是必须win;

另外这个题目还有一个点是, 要你分析复杂度; 这个是作者的观点:

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][1].

因为加了memo, 所以最后的复杂度不再是指数级(N^N), 而是N? number of possible strings? 不对哦! 这个425的时候学过了, 严格来说应该是所有不同的string对应的自己的fanning之和(每一个distinct string其实只有一次fan out的机会(在这之后的call全都被memo给直接快速处理了));

因为这题所有的fanning统一都是N, 所以关键还是找到有多少个distinct strings (这里不需要用到aggregate分析的方法);

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

这个就是inspire我自己的解法的discussion最优解版本; 这个是没有memo的, 不过基本思路你是看得到的; 这个代码逻辑还是很清晰的, 难得;

discussion还有一个这样的:

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

这个其实是差不多的东西, 不过就是非要先做出来一个list来装这些东西而已; 但是这个好像是能加速的, 因为这个是在一个char array的基础上生成了所有的next strings, 所以为了生成每一个string, 所需要的时间其实是O(1). 不对, 不是, 虽然flip的操作是O(1), 但是String.valueOf好像其实还是O(N)? 搜了一下, 好像没有找到结果;

另外, 这里的memo, 用HashMap其实不是最好的做法:

Since we only save string who is true, we can use HashSet in stead to save time and space.

这个想法是对的, 因为我们这里的value是binary的, 所以干脆可以直接用contains来模拟就行了; 这个肯定能节省space; 节省time的话, 感觉效果比较微小;

另外这一题也教了一个东西: memo这个并不是只属于DP的专利, 所有的DFS都可以用, 包括backtracking;

我现在, 就这个问题来说, 感觉DP跟backtracking的一个区别可以是:

• backtracking我们手上拿的始终是size相同的input, 只不过当中有些entry被改变;
• DP当中, 我们要有一个subproblem的概念, furthermore, smaller problems. 所以DP的时候, 往往这个input的size在recursion的过程中会不断降低;

discussion最火的一个帖子给出的是一个基于game theory的做法; 通过应用一个写game theory的理论, 最终复杂度可以提高到N^2; 好像下面的两个submission最优解就是这个思路, 这也是为什么它们能这么快;

Can we even do better than that? Sure! Below I'll show the time complexity can be reduced to O(N^2) using Dynamic Programming, but the improved method requires some non-trivial understanding of the game theory, and therefore is not expected in a real interview. If you are not interested, please simply skip the rest of the article:

---

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.

意思就是moves和胜利条件要一样. 记住chess这个例子;

--

Concept 2 (Normal Play vs Misere Play): If the winning condition of
the game is that the opponent 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.

好像捣台球是misere? 捣台球同时好像也是impartial; 注意判断impartial的same moves的时候, 是指的比如当前这一步, 无论我是先动方还是后手方, 我的move都一样; 而不是说先动方动了一下, 然后后手方也动了一下, 然后这两个move一样: 这个显然是不可能的;

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.

In order to simplify the solution, we still need to understand one more concept:

Concept 3 (Sprague-Grundy Function): Suppose x represents a particular
arrangement of board, and x_0, x_1, x_2, ... ,x_k represent the board
after a valid move, then we define the Sprague-Grundy function as:

 g(x) = FirstMissingNumber(g(x_0), g(x_1), g(x_2), ... , g(x_k)).   

where FirstMissingNumber(y) stands for the smallest positive number
that is not in set y. For instance, if g(x_0) = 0, g(x_1) = 0, g(x_k) =
2, then g(x) = FMV({0, 0, 2}) = 1.

Why do we need this bizarre looking S-G function? Because we can instantly decide whether 1P has a winning move simply by looking at its value. I don't want to write a book out of it, so for now, please simply take the following theorem for granted:

Theorem 1: If g(x) != 0, then 1P must have a guaranteed winning move
from board state x. Otherwise, no matter how 1P moves, 2P must then
have a winning move.

So our task now is to calculate g(board). But how to do that? Let's first of all find a way to numerically describe the board. Since we can only flip ++ to --, then apparently, we only need to write down the lengths of consecutive ++'s of length >= 2 to define a board. For instance, ++--+-++++-+----- can be represented as (2, 4).
之所以选择length ≥ 2是因为, length0的肯定是不考虑的, length1的也可以不考虑, 因为下一手你是没有办法在这个run上面发生任何的flip的;

(2, 4) has two separate '+' subsequences. Any operation made on one subsequence does not interfere with the state of the other. Therefore, we say (2, 4) consists of two subgames: (2) and (4).
这个sub跟DP的subproblem里面的sub的定义有所区别: DP的subproblem定义是允许overlapping的. 不过还是按照这里的设定来: subgame之间要disjoint/independent;

Okay now we are only one more theorem away from the solution. This is the last theorem. I promise:

Theorem 2 (Sprague-Grundy Theorem): The S-G function of game x = (s1,
s2, ..., sk) equals the XOR of all its subgames s1, s2, ..., sk. e.g.
g((s1, s2, s3)) = g(s1) XOR g(s2) XOR g(s3).

这个作者是后面补充的一个解释:
In my understanding, the S-G function basically says: If ANY subsequent state of state x is a losing position (g == 0), then x itself must be a winning position (g != 0); if ALL subsequent states are winning positions (g!=0), then x must be a losing position (g ==0). The above 2 situations can be unified by a FirstMissingNumber operation. For any normal impartial game, simply find out all states x_0, x_1, ... x_k reachable from a state x, then use Concept 3 and Theorem 2 to calculate S-G function.

Sorry my knowledge of Game Theory is rather superficial. Hope it helps.

With the S-G theorem, we can now compute any arbitrary g(x). If x contains only one number N (there is only one '+' subsequence), then

g(x) = FMV(g(0, N-2), g(1, N-3), g(2, N-4), ... , g(N/2-1, N-N/2-2));  
     = FMV(g(0)^g(N-2), g(1)^g(N-3), g(2)^g(N-4)), ... g(N/2-1, N-N/2-2));  

Now we have the whole algorithm:

Convert the board to numerical representation: x = (s1, s2, ..., sk)  
Calculate g(0) to g(max(si)) using DP.  
if g(s1)^g(s2)^...^g(sk) != 0 return true, otherwise return false.  

Calculating g(N) takes O(N) time (N/2 XOR operations plus the O(N) First Missing Number algorithm). And we must calculate from g(1) all the way to g(N). So overall, the algorithm has an O(N^2) time complexity.

Naturally, the code is bit more complicated than the backtracking version. But it reduces the running time from ~128ms to less than 1ms. The huge improvement is definitely worth all the hassle we went through.

这个是作者原来自己写的代码:

int firstMissingNumber(unordered_set<int> lut) {  
    int m = lut.size();  
    for (int i = 0; i < m; ++i) {  
        if (lut.count(i) == 0) return i;  
    }  
    return m;  
}  

bool canWin(string s) {  
    int curlen = 0, maxlen = 0;  
    vector<int> board_init_state;  
    for (int i = 0; i < s.size(); ++i) {      
        if (s[i] == '+') curlen++;              // Find the length of all continuous '+' signs  
        if (i+1 == s.size() || s[i] == '-') {  
            if (curlen >= 2) board_init_state.push_back(curlen);    // only length >= 2 counts  
            maxlen = max(maxlen, curlen);       // Also get the maximum continuous length  
            curlen = 0;  
        }  
    }          // For instance ++--+--++++-+ will be represented as (2, 4)  
    vector<int> g(maxlen+1, 0);    // Sprague-Grundy function of 0 ~ maxlen  
    for (int len = 2; len <= maxlen; ++len) {  
        unordered_set<int> gsub;    // the S-G value of all subgame states  
        for (int len_first_game = 0; len_first_game < len/2; ++len_first_game) {  
            int len_second_game = len - len_first_game - 2;  
            // Theorem 2: g[game] = g[subgame1]^g[subgame2]^g[subgame3]...;  
            gsub.insert(g[len_first_game] ^ g[len_second_game]);  
        }  
        g[len] = firstMissingNumber(gsub);  
    }  

    int g_final = 0;  
    for (auto& s: board_init_state) g_final ^= g[s];  
    return g_final != 0;    // Theorem 1: First player must win iff g(current_state) != 0  
 }

下面两个是对于这个代码的改写;

reminder: 这里FMN函数是helper, 所以先从main函数, 也就是canWin函数开始读比较有助于理解;

这个是submission最优解:1(99)

public class Solution {      
    public boolean canWin(String s) {  
        int curLen = 0, maxLen = 0;  
        List<Integer> list = new ArrayList<>();  
        for (int i = 0; i < s.length(); i++) {  
            if (s.charAt(i) == '+') curLen++;  
            if (s.charAt(i) == '-' || i == s.length() - 1) {  
                if (curLen >= 2)  list.add(curLen);  
                maxLen = Math.max(maxLen, curLen);  
                curLen = 0;  
            }  
        }  
        int[] g = new int[maxLen + 1];  
        for (int len = 2; len <= maxLen; len++) {  
            Set<Integer> set = new HashSet<>();  
            for (int first = 0; first < len / 2; first++) {  
                int second = len - first - 2;  
                set.add(g[first] ^ g[second]);  
            }  
            g[len] = FMV(set);  
        }  
        int res = 0;  
        for (int i : list) res ^= g[i];  
        return res != 0;  
    }  

    private int FMV(Set<Integer> set) {  
        int i = 0;  
        for (; i < set.size(); i++) {  
            if (!set.contains(i)) break;  
        }  
        return i;  
    }  
}

这个速度真的过分了, 比backtracking快太多了;

• 第一个循环是一个简洁的分段算法: 记录所有的'+'run的长度; 并且记录最长的一个长度, 后面计算的时候使用; 比如当前的棋盘是(2,3,4), 那么最后g(2,3,4) = g(2) xor g(3) xor g(4). 下面就是要计算这几个值;
• 第二个循环就是用一个Bottom-Up的DP算法来计算g(i) for all i. maxLen在这里就发挥作用了: 控制iteration的长度;
  • 注意inner for循环的终点: < N/2: 这个在很多类似的对称循环当中是一个可以用的技巧, 很简练;
  • g[first] ^ g[second]是体现DP精神的关键: first和second都是确定的比当前要算的len要小的, 所以只要我们用Bottom-Up的方式, 在这一步(len)的时候, 我们肯定已经知道这两个值了;
• 最后一步就是把g(2,3,4) = g(2) xor g(3) xor g(4)组合起来计算, 然后判断是否等于0就行了;

这里刚开始可能有点疑惑, 因为这里g这个函数实际上用了两个公式来计算:

g(x) = FirstMissingNumber(g(x_0), g(x_1), g(x_2), ... , g(x_k)) //出现在第二部分  
g((s1, s2, s3)) = g(s1) XOR g(s2) XOR g(s3) //出现在第一和第三部分

另外注意看g的长度的+1: 这个真的是老生常谈了;

另外一个submission最优解:3(98)

public class Solution {  

    public boolean canWin(String s) {  
        s = s.replace('-', ' ');  
        int G = 0;  
        List<Integer> g = new ArrayList<>();  
        for (String t : s.split("[ ]+")) {  
            int p = t.length();  
            if (p == 0) continue;  
            while (g.size() <= p) {  
                char[] x = t.toCharArray();  
                int i = 0, j = g.size() - 2;  
                while (i <= j)  
                    x[g.get(i++) ^ g.get(j--)] = '-';  
                g.add(new String(x).indexOf('+'));  
            }  
            G ^= g.get(p);  
        }  
        return G != 0;  
    }  
}

这个是正则先锋Stefan改写的版本: 把'-'替换掉了这样split更方便一些; 还有一些其他的改进:

• 用list而非array来作为memo; 这样的一个好处好像是可以直接用这个list的size来判断第二环节的计算;
• 用char array和string的操作来完成一个FMV的功能; 这个其实是蛮聪明的; 看起来很简洁, 虽然实际上的速度未必比原版直接结算的要快.

尽管如此, 这个算法还是一个N^2的算法, 所以最后还是遥遥领先;

@StefanPochmann said in Theory matters - from Backtracking(128ms) to DP (0ms):

I don't remember seeing it in class, either, probably only know it due to coding competitions or so. In this case, before seeing stellari's article, I had gotten as far as this OEIS page by computing the first few of those losing numbers with a backtracking solution and then searching for them there.

Ooohhh... now I also looked for the sequence of g-numbers, found it, and it's periodic with just a few small exceptions. Thus we can use this to get an O(n) algorithm! stellari, do you want to include that in your article?

Stefan的一个评论的意思是, 这个问题甚至可以找到O(N)的算法; 不过他们后面好像没有完成这个东西;

Problem Description

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.

For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm's runtime complexity.

Difficulty:Medium
Total Accepted:26.1K
Total Submissions:56.3K
Contributor: LeetCode
Companies
google
Related Topics
backtracking
Similar Questions
Nim Game Flip Game Guess Number Higher or Lower II Can I Win

Problem Description

这个是我发在discussion上面关于复杂度的讨论:

@jeantimex I do not quite agree with you analysis of the complexity.

First, even with memoization, the time cost is not necessarily O(N), with N being the number of distinct strings that could result from flipping. It is correct that each unique string will only get calculated once by courtesy of memoization, but that one time calculation does not necessarily only require O(1). Actually, in this algorithm, we have to loop over N-1 indices for each such unique string's first time computation, and in some of these iterations, we have to construct a length N string (in worst case like ++++..., we construct it for each index/iteration). So propose that the complexity should be number_of_distinct_strings * N^2.

Note that this N^2 part is not tight: even for a worst case like ++++..., it is not possible that every distinct string will do N iterations which all construct the length N string for recursive calls. Because the deeper this string is within the recursion tree, the more - there are in the string, and the less likely the string-construction thing is gonna be triggered. If a string is one level deeper (experienced one more flip), then number of next-strings it need to construct will decrease by 1. It is possible that we will be able to say the bound is tight in hope of something like 1 + 2 + 3 + ... + N = O(N^2) happening, but this is just not for sure: I do not know for certain the distribution so far. It's a tree after all, and it is likely that there will be far more strings that construct less next-strings, which goes in favor of my conjecture that this N^2 thing is not tight.

Now, to compute the number_of_distinct_strings: @jeantimex proposed a solution of O(N!!). I here propose O(2^N). According to something I found, we have (2N)!! = 2^N * N!, and thus N!! = 2^(N/2) * (N/2)! (is this right?)
which is larger than 2^(N/2) * 2^(N/2) = 2^N.
Side note: possible reasons that Jean's proposition is not tight:

• For cases like this: for ++++++++, we first flip it to ++--++++, then to ++----++. But if we first flip it to ++++--++, then also flip to ++----++. The string ++----++ is counted twice in these two different recursion paths, while there occupy the same entry in the memoization map.
• Still for the case of ++++++++ of length 8. We first have N - 1 = 7 positions for the first flip as proposed by jean. Suppose we flip it to ++--++++. Do we have N-2 -1 = 5 positions to place the second flip? Not likely. We can't view the string after the first flip as ++++++, which would have N-2-1=5 positions for the next flip. Because the introduced -- essentially blocked the two + on left and right, and these two + can't contribute one position for the next flip to be at.

To get this result of O(2^N): let's consider, starting from a worst case like ++++... of length N, how many flips we already created on it. Each flip introduce a -- into the string. Suppose the N is 10:

• how many 1-flip strings do we have: P(9,1). Because we can view -- together as one entry, so we have a length 9 sequence. All left to be decided is where to fit this -- entry;
• How many 2-flip strings? We have two -- entries now, in a length 8 sequence (of all elements of the sequence: 2 -- and 6 +: 10 - 2 = 6 + 2 * 2, the total number of characters is still 10). The number is P(8,2).

and so on.
The total sum of number of i-flip strings is: P(9,1) + P(8,2) + P(7,3) + P(6,4) + P(5,5).

Side note: Note the above analysis ignored some corner cases: for example, in a 2-flip situation, we might have +(--)++++... after we placed the first flip (or the -- element). This placement in essence nullifies the + at position 0 and changed the total length to 7 rather than 8. But I don't think these cases are significant enough.

I have a feeling that there might be a math thing for this (sum of P(i,j) where i + j = N), but I just don't know. So I will have to un-tighten them again:

  P(9,1) + P(8,2) + P(7,3) + P(6,4) + P(5,5)  
≤ P(10,1) + P(10,2) + P(10,3) + P(10,4) + P(10,5) + ... + P(10,10)  
= 2 ^ 10 - P(10,0) //(similar to calculating how many values from a 10-bit binary)

So for the case of N, we can say the number_of_distinct_strings is O(2^N). You can squeeze in a factor of 2 here because we actually doubled the length of summation from 5 to 10, and the two length-5 halves are symmetric. But it's not significant.

In conclusion, I propose the total complexity to be

  number_of_distinct_strings * each_unique_string_first_time_computation_contribution  
= O(2^N) * O(N^2)  
= O(2^N * N^2)

Also I admit this is not a very rigorous proof:

• why is ++++... necessarily the worst case?
• the computation of O(N^2) is not tight
• the computation of O(2^N) is not tight
• the +(--)+++.. corner cases

Hope this helps.