Java Recursive, simple backtracking,


  • 1
    P
    public class Solution {
    public boolean canWin(String s) {
        if(s == null || s.length() <= 1)
            return false;
        return dfs(s);
    }
    
    public boolean dfs(String s) {
        for(int i = 0; i < s.length() - 1; i++)
        {
            if(s.charAt(i) == '+' && s.charAt(i + 1) == '+')
            {
                char[] cA == s.toCharArray();
                cA[i] = '-';
                cA[i + 1] = '-';
                String cur = new String(cA);
                if(!dfs(cur))
                    return true;
            }
        }
        
        //can not flip
        return false;
    }
    

    }

    to avoid duplicate state check, could save states in two sets(firstWin state set and second win state set)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.