Memoization
Math
Dynamic Programming
Backtracking
Game Theory
Description
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.
Example 1:
Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Example 2:
Input: currentState = "+"
Output: false
Constraints:
1 <= currentState.length <= 60
currentState[i]
is either '+'
or '-'
.
Follow up: Derive your algorithm's runtime complexity.
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def canWin ( self , currentState : str ) -> bool :
@cache
def dfs ( mask ):
for i in range ( n - 1 ):
if ( mask & ( 1 << i )) == 0 or ( mask & ( 1 << ( i + 1 )) == 0 ):
continue
if dfs ( mask ^ ( 1 << i ) ^ ( 1 << ( i + 1 ))):
continue
return True
return False
mask , n = 0 , len ( currentState )
for i , c in enumerate ( currentState ):
if c == '+' :
mask |= 1 << i
return dfs ( mask )
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
30
31
32
33 class Solution {
private int n ;
private Map < Long , Boolean > memo = new HashMap <> ();
public boolean canWin ( String currentState ) {
long mask = 0 ;
n = currentState . length ();
for ( int i = 0 ; i < n ; ++ i ) {
if ( currentState . charAt ( i ) == '+' ) {
mask |= 1 << i ;
}
}
return dfs ( mask );
}
private boolean dfs ( long mask ) {
if ( memo . containsKey ( mask )) {
return memo . get ( mask );
}
for ( int i = 0 ; i < n - 1 ; ++ i ) {
if (( mask & ( 1 << i )) == 0 || ( mask & ( 1 << ( i + 1 ))) == 0 ) {
continue ;
}
if ( dfs ( mask ^ ( 1 << i ) ^ ( 1 << ( i + 1 )))) {
continue ;
}
memo . put ( mask , true );
return true ;
}
memo . put ( mask , false );
return false ;
}
}
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 using ll = long long ;
class Solution {
public :
int n ;
unordered_map < ll , bool > memo ;
bool canWin ( string currentState ) {
n = currentState . size ();
ll mask = 0 ;
for ( int i = 0 ; i < n ; ++ i )
if ( currentState [ i ] == '+' ) mask |= 1l l << i ;
return dfs ( mask );
}
bool dfs ( ll mask ) {
if ( memo . count ( mask )) return memo [ mask ];
for ( int i = 0 ; i < n - 1 ; ++ i ) {
if (( mask & ( 1l l << i )) == 0 || ( mask & ( 1l l << ( i + 1 ))) == 0 ) continue ;
if ( dfs ( mask ^ ( 1l l << i ) ^ ( 1l l << ( i + 1 )))) continue ;
memo [ mask ] = true ;
return true ;
}
memo [ mask ] = false ;
return false ;
}
};
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 func canWin ( currentState string ) bool {
n := len ( currentState )
memo := map [ int ] bool {}
mask := 0
for i , c := range currentState {
if c == '+' {
mask |= 1 << i
}
}
var dfs func ( int ) bool
dfs = func ( mask int ) bool {
if v , ok := memo [ mask ]; ok {
return v
}
for i := 0 ; i < n - 1 ; i ++ {
if ( mask & ( 1 << i )) == 0 || ( mask & ( 1 << ( i + 1 ))) == 0 {
continue
}
if dfs ( mask ^ ( 1 << i ) ^ ( 1 << ( i + 1 ))) {
continue
}
memo [ mask ] = true
return true
}
memo [ mask ] = false
return false
}
return dfs ( mask )
}
Solution 2
GitHub