[LeetCode] Flip Game II

294. Flip Game II

You are playing a Flip Game with your friend.

You are given a string currentState that contains only ‘+’ 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.

Return true if the starting player can guarantee a win, and false otherwise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
unordered_map<string, bool> dp[2];
bool solution(string& status, bool turn) {
if(dp[turn].count(status)) return dp[turn][status];
dp[turn][status] = !turn;
for(int i = 0; i < status.length() - 1 and dp[turn][status] == !turn; i++) {
if(status[i] == '+' and status[i+1] =='+') {
status[i] = status[i+1] = '-';
bool res = solution(status,!turn);
status[i] = status[i+1] = '+';
dp[turn][status] = res;
}
}
return dp[turn][status];
}
public:
bool canWin(string currentState) {
return solution(currentState, true);
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/19/PS/LeetCode/flip-game-ii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.