Easy to understand neat Java solution using Hashset.


  • 0
    P
    public class Solution {
    
    Set<String> seen = new HashSet<>(); // contains winning moves.
    	public boolean canWin(String s) {
    		if(seen.contains(s))
    			return true;
    		List<String> moves = generatePossibleNextMoves(s);
    		for(String move : moves) {
    			if(!canWin(move)) { // If any of the next move lead to the sure shot loss of next player then take it and win.
    				seen.add(s); 
    				return true; 
    			}
    		}		
    		return false;
    	}
    	
    	public List<String> generatePossibleNextMoves(String s) { // Easy one.
    		if (s.length() == 0)
    			return new ArrayList<>();
    		List<String> res = new ArrayList<>();
    		char[] chs = s.toCharArray();
    		for (int i = 0; i < chs.length - 1; i++) {
    			if (chs[i] == '+' && chs[i + 1] == '+') {
    				chs[i] = '-';
    				chs[i + 1] = '-';
    				res.add(String.valueOf(chs));
    				chs[i] = '+'; // Put back stuffs.
    				chs[i + 1] = '+';
    			}
    		}
    		return res;
                }
    	}
    

Log in to reply
 

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