My 21ms java solution with the DP idea and use static class variable


  • 0
    S
    public class Solution {
        private static Map<String, Boolean> winMap = new HashMap<>();
        public boolean canWin(String s) {
            for(int i=1; i<s.length(); i++){
                if(s.charAt(i)=='+'&&s.charAt(i-1)=='+'){
                    String left = i-2<0?"":s.substring(0,i-1);
                    String right = i+1>=s.length()?"":s.substring(i+1,s.length());
                    String temp = left+"--"+right;
                    if(winMap.containsKey(temp)){
                            if(winMap.get(temp)){
                                continue;
                            }else{
                                winMap.put(s,true);
                                return true;
                            }
                        }else{
                            if(!canWin(temp)){
                            winMap.put(temp,false);
                            winMap.put(s,true);
                            return true;
                                }
                            else{
                            winMap.put(temp,true);
                            continue;
                                }
                        }
                }
             }
                    winMap.put(s,false);
                    return false;
        }
    }
    

Log in to reply
 

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