# Share my Java backtracking solution

• The idea is try to replace every "++" in the current string s to "--" and see if the opponent can win or not, if the opponent cannot win, great, we win!

For the time complexity, here is what I thought, let's say the length of the input string s is n, there are at most n - 1 ways to replace "++" to "--" (imagine s is all "+++..."), once we replace one "++", there are at most (n - 2) - 1 ways to do the replacement, it's a little bit like solving the N-Queens problem, the time complexity is (n - 1) x (n - 3) x (n - 5) x ..., so it's O(n!!), double factorial.

That's what I thought, but I could be wrong :)

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;
}

• Great explanations!

• This post is deleted!

• Clean solution, easy to understand!

• Great solution! One improvement: adding memorization (HashSet) will greatly reduce time complexity. Although game theory can do much better, I think the following solution is very ideal for an interview. This is a 21ms solution:

public boolean canWin(String s) {
if(s == null || s.length() < 2) return false;

Set<String> winSet = new HashSet<String>();
return canWin(s, winSet);
}

public boolean canWin(String s, Set<String> winSet){
if(winSet.contains(s)) return true;

for(int i = 0; i < s.length() - 1; i++) {
if(s.charAt(i) == '+' && s.charAt(i + 1) == '+') {

String sOpponent = s.substring(0, i) + "--" + s.substring(i + 2);
if(!canWin(sOpponent, winSet)) {
return true;
}
}
}
return false;
}

• s.charAt(i) == '+' && s.charAt(i + 1) == '+' can be shorten as s.startsWith("++", i)

• Thanks @jeantimex. I actually tried s.startsWith("++", i) the run time is a bit slower and it's calling a convenient API. Anyway both are fine for an interview.

I even tried to eliminate substring but it looks like converting to string using new String(charArray) greatly increase the time cost.

• Ok, in your solution, you only cache the win set, in my opinion we can also cache the lose set, and we can use a Map <String, Boolean> to help with that.

• Thanks to @jeantimex. If we use HashMap to memorize both win string & lose string, we can further reduce time from 208ms to 18ms:

public boolean canWin(String s) {
if(s == null || s.length() < 2) return false;
Map<String, Boolean> map = new HashMap<>();
return canWin(s, map);
}

public boolean canWin(String s, Map<String, Boolean> map){
if(map.containsKey(s)) return map.get(s);
for(int i = 0; i < s.length() - 1; i++) {
if(s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
String opponent = s.substring(0, i) + "--" + s.substring(i + 2);
if(!canWin(opponent, map)) {
map.put(s, true);
return true;
}
}
}
map.put(s, false);
return false;
}

• You are right. We should also cache the lost case. I've posted the Map<String, Boolean> version and the time reduced by 14.3%.

• Excellent! :)

• This solution is now "Time Limit Exceeded"...

• How can I visually understand this solution? It's hard to imagine.

• Could you please analyze the time complexity?

• This is really good! Thanks!

• I think this solution reduce the complexity from factorial to exponential. With memorization, the complexity depends on how many states the string can be changed to .

• Can you please explain, what will be the time complexity of this ?

• Could you please explain why canWin() returns true means player 1 is guaranteed to have a winning strategy? Don't we need to check when no move can be made is the current player the player 1 or player 2?

• So what if the input is ++++?

Then say the first player flips the first two, so it becomes --++
Then the second player flips the next two so it is ----
SO in this specific recursion path, the function should return that the first player cannot win, right? However, when you recur onto ----, the function will return false, which gets negated into True, which suggests that the first player can win when really he cannot.

• Same approach here:

public class Solution {
public boolean canWin(String s) {
if (s == null || s.length() < 2) {
return false;
}
for (String next : generatePossibleNextMoves(s)) {
if (!canWin(next)) {
return true;
}
}

return false;
}

public List<String> generatePossibleNextMoves(String s) {
List<String> result = new ArrayList<String>();
if (s == null || s.length() < 2) {
return result;
}
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length - 1; i++) {
if (chars[i] == '+' && chars[i + 1] == '+') {
chars[i] = '-';
chars[i + 1] = '-';