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.

Analysis

只有在flip之后对方无法保证赢的情况下，自己这一方才有可能保证赢。因此子问题便是，每次对"++"变形flip为“--”之后，新的字符串是否能保证赢？

对子问题的搜索是可能有重复的，因此结合记忆化memoization，就可以解决这个问题。

定义辅助函数

boolean canWinHelper(String s, HashMap<String, Boolean> map)

返回的boolean代表对于string s，是否能够保证赢 （guarantee a win）。

对于题中所给的例子，搜索树search tree示意图(字符串代表搜索函数的输入值，结果在括号中，T = true, F = false)：

             "++++" (T)
        /       |       \
  "--++" (T) "+--+" (F)  "++--" (T)
    /                      \  
"----" (F)                "----" (F)

Time Complexity

DFS记忆化搜索时间复杂度近似：Big O

O(状态数*计算每个状态所需时间)

对于这一类记忆化搜索问题计算复杂度，一般计算复杂度的上界（采用大O符号）。我们采取的计算公式为，复杂度 = 状态数 * 决策数目 * 转移费用。

状态数上界为O(2^n)，决策数目上界为O(n)，转移费用为O(1)，因此复杂度上界为O(n*2^n)

Solution

Search + memoization (6ms 97.22%)

class Solution {
    public boolean canWin(String s) {
        char[] arr = s.toCharArray();
        HashMap<String, Boolean> map = new HashMap<String, Boolean>();
        return canWinHelper(s, map);
    }

    public boolean canWinHelper(String s, HashMap<String, Boolean> map) {
        if (s == null || s.length() == 0) return false;
        if (map.containsKey(s)) return map.get(s);
        char[] arr = s.toCharArray();
        boolean canWin = false;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] == '+' && arr[i + 1] == '+') {
                arr[i] = '-';
                arr[i + 1] = '-';
                boolean search = canWinHelper(new String(arr), map);
                if (!search) {
                    canWin = true;
                    break;
                }
                arr[i] = '+';
                arr[i + 1] = '+';
            }
        }
        map.put(s, canWin);
        return canWin;
    }
}

Reference

https://mnmunknown.gitbooks.io/algorithm-notes/flip_game.html

https://leetcode.com/problems/flip-game-ii/discuss/73954/Theory-matters-from-Backtracking(128ms)-to-DP-(0ms\)

Time complexity estimation: https://www.jiuzhang.com/qa/1775/

https://www.jiuzhang.com/qa/6511/