-
Notifications
You must be signed in to change notification settings - Fork 3
/
294.cpp
22 lines (22 loc) · 766 Bytes
/
294.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
unordered_map<string, bool> memo;
bool win(string& currentState) {
if (memo.find(currentState) != memo.end()) return memo[currentState];
for (int i = 0; i < currentState.size() - 1; ++i) {
if (currentState[i] == '+' && currentState[i + 1] == '+') {
bool flag = false;
currentState[i] = '-';
currentState[i + 1] = '-';
flag = !win(currentState);
currentState[i] = '+';
currentState[i + 1] = '+';
if (flag) return memo[currentState] = true;
}
}
return memo[currentState] = false;
}
bool canWin(string currentState) {
return win(currentState);
}
};