Comment on page
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.
只有在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)
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;
}
}
Last modified 3yr ago