JAVA DP BEAT 98%


  • 0
    H
    class Solution {
    	Map<String, Boolean> mv;
    
    	public boolean canWin(String s) {
    		if (s == null || s.length() < 2)
    			return false;
    		mv = new HashMap<>();
    		String[] ss = s.split("-");
    		Map<Integer, Integer> info = new HashMap<>();
    		for (String s1 : ss) {
    			info.put(s1.length(), info.getOrDefault(s1.length(), 0) + 1);
    		}
    		return canwinhelper(info);
    	}
    
    	private boolean canwinhelper(Map<Integer, Integer> info) {
    		if (mv.containsKey(info.toString())) {
    			return mv.get(info.toString());
    		}
    		if (info.size() == 0) {
    			return false;
    		}
    		int c, l, r;
    		boolean res = false;
    		Set<Integer> set = new HashSet<>(info.keySet());
    		for (int i : set) {
    			c = info.get(i);
    			if (c == 1) {
    				info.remove(i);
    			} else {
    				info.put(i, c - 1);
    			}
    
    			for (int j = 0; j < i && j <= i - j - 2; j++) {
    				l = j;
    				r = i - j - 2;
    				update2355(info, l);
    				update2355(info, r);
    				res = canwinhelper(info);
    				update2365(info, l);
    				update2365(info, r);
    				if (!res) {
    					info.put(i, c);
    					mv.put(info.toString(), true);
    					return true;
    				}
    			}
    
    			info.put(i, c);
    		}
    
    		mv.put(info.toString(), false);
    		return false;
    	}
    
    
    
    	private void update2355(Map<Integer, Integer> info, int l) {
    		if (l > 1) {
    			info.put(l, info.getOrDefault(l, 0) + 1);
    		}
    	}
    
    	private void update2365(Map<Integer, Integer> info, int l) {
    		if (l > 1) {
    			if (info.get(l) == 1) {
    				info.remove(l);
    			} else {
    				info.put(l, info.get(l) - 1);
    			}
    		}
    	}
    
    }
    

Log in to reply
 

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