Flip Game Ii - Leetcode Solution

Problem Statement:

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.

Solution:

This problem requires us to implement a backtracking algorithm with memoization to avoid redundant calculations. We will start by initializing a memo dictionary to store the results of the subproblems.

For each subproblem, we will loop through the string and find all the consecutive "++" substrings. For each substring, we will flip it to "--" and make a recursive call with the updated string.

If the recursive call returns False, it means that the other player can guarantee a win with the current updated string state. In that case, we will set the current state to True.

After looping through all the substrings, we will return the memoized result of the current state.

Code:

def canWin(s):

memo = {}
return helper(s, memo)

def helper(s, memo):

if s in memo:
    return memo[s]

for i in range(len(s)-1):
    if s[i:i+2] == "++":
        updated = s[:i] + "--" + s[i+2:]
        if not helper(updated, memo):
            memo[s] = True
            return True

memo[s] = False
return False

Time Complexity: O(n^2)

Space Complexity: O(n^2)

Explanation:

We start by initializing a memo dictionary to store the results of the subproblems. The canWin function calls the helper function with the input string and memo dictionary.

The helper function checks if the final state of the input string is already memoized. If so, it returns the memoized result.

For each subproblem, the helper function loops through the input string and finds all the consecutive "++" substrings. For each substring, it creates a new string with that substring flipped to "--".

The helper function makes a recursive call with this updated string. If the recursive call returns false, it means that the other player can guarantee a win with the current updated string state. In that case, we set the current state to True and return True.

If no substrings are left to flip, we return False as no moves can be made and therefore the current player cannot guarantee a win.

After looping through all the substrings, we memoize the current state and return the result.

1