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