-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFlip_Game_II.java
More file actions
29 lines (20 loc) · 912 Bytes
/
Copy pathFlip_Game_II.java
File metadata and controls
29 lines (20 loc) · 912 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
294. 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 twoconsecutive "++" 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.
For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Follow up:
Derive your algorithm runtime complexity.
public boolean canWin(String s) {
if (s == null || s.length() < 2) {
return false;
}
for (int i = 0; i < s.length() - 1; i++) {
if (s.startsWith("++", i)) {
String t = s.substring(0, i) + "--" + s.substring(i + 2);
if (!canWin(t)) {
return true;
}
}
}
return false;
}