Easily understandable backtrack solution


  • 2
    S
    public class Solution {
        public boolean canWin(String s) {
            
            
            for(int i=0;i<s.length()-1;i++)
            {
                if(s.charAt(i)=='+' && s.charAt(i+1)=='+')
                {
                    if(!canOpponentWin(s.substring(0,i)+"--"+s.substring(i+2)))
                    return true;
                }
            }
            
            return false;
            
        }
        
        private boolean canOpponentWin(String s)
        {
            for(int i=0;i<s.length()-1;i++)
            {
                if(s.charAt(i)=='+' && s.charAt(i+1)=='+')
                {
                    if(!canWin(s.substring(0,i)+"--"+s.substring(i+2)))
                    return true;
                }
            }
            
            return false;
        }
    }

  • 2
    J

    This two methods are the same. Why not just recursive yourself

    public boolean canWin(String s) {

    for(int i=0;i<s.length()-1;i++)
    {
        if(s.charAt(i)=='+' && s.charAt(i+1)=='+')
        {
            if(!canWin(s.substring(0,i)+"--"+s.substring(i+2)))
            return true;
        }
    }
    
    return false;
    

    }


Log in to reply
 

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