Leetcode #294. Flip Game II

[yokostan]

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

If we use HashMap based on the above solution, we can get 10 times faster by memorizing the permutations we already judged.

class Solution {
    public boolean canWin(String s) {
        if (s == null || s.length() < 2) return false;
        Map<String, Boolean> map = new HashMap<String, Boolean>();
        return helper(s, map);
    }

    public boolean helper(String s, Map<String, Boolean> map) {
        if (map.containsKey(s)) {
            return map.get(s);
        }
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '-') continue;
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                String s2 = s.substring(0, i) + "--" + s.substring(i + 2);
                if (!helper(s2, map)) {
                    map.put(s, true);
                    return true;
                }
            }
        }
        map.put(s, false);
        return false;
    }
}

[yokostan]

Also, we can use s.startsWith("++", i) to replace the condition statement.

[yokostan]

The HashMap eliminates duplicate steps in between.