294. Flip Game II

二刷
Bug -> flag == ture的时候break, break之前没有reset array
注意backtracking 的所有出口，所有，不管是成功或者失败，都要reset status
96.98 % 
class Solution {
    public boolean canWin(String s) {
        if (s == null || s.length() == 0) return false;
        return helper(s.toCharArray(), new HashMap<>());
    }
   
    private boolean helper(char[] array, Map<String, Boolean> map) {
        boolean flag = false;
        for (int i = 1; i < array.length; i++) {
            // Try all flip possibilities, if one can make the next persion lose, then return true
            if (array[i] == '+' && array[i - 1] == '+') {
                array[i] = '-';
                array[i - 1] = '-';
                String curr = new String(array);
                if (!map.containsKey(curr)) {
                    map.put(curr, helper(array, map));
                }
                array[i] = '+';
                array[i - 1] = '+';
                if (map.get(curr) == false) {
                    flag = true;
                    break;
                }
            }
        }
        return flag;
    }
}

一刷
两个人同样聪明
如果能保证对手必输，则return true
如果对手能保证赢，则return false
这个题也是可以memorized
Version #1 Without Memorization
65.63 %
public class Solution {
    public boolean canWin(String s) {
        if (s == null && s.length() <= 2) return true;
        char[] chars = s.toCharArray();
        return canWin(chars);
    }
    //For every possible move, if there's one can make the competitor return false, then we can return true. Otherwise, return false
    private boolean canWin(char[] chars) {
        boolean result = false;
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] == '+' && chars[i + 1] == '+') {
                chars[i] = '-';
                chars[i + 1] = '-';
                if (canWin(chars) == false) result = true;
                //Set back
                chars[i] = '+';
                chars[i + 1] = '+';
            }
            if (result) return true;
        }
        return false;
    }
}

Version #2 Memorization with hashmap
93.75 %
If we see the same string that we have checked before, we can return that result directly

public class Solution {
    public boolean canWin(String s) {
        if (s == null && s.length() <= 2) return true;
        char[] chars = s.toCharArray();
        return canWin(chars, new HashMap<String, Boolean>());
    }
    //For every possible move, if there's one can make the competitor return false, then we can return true. Otherwise, return false
    private boolean canWin(char[] chars, Map<String, Boolean> visited) {
        Boolean haveVisited = visited.get(new String(chars));
        if (haveVisited != null) return haveVisited;
     
        boolean result = false;
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] == '+' && chars[i + 1] == '+') {
                chars[i] = '-';
                chars[i + 1] = '-';
                if (canWin(chars, visited) == false) {
                    result = true;
                }
                //Set back
                chars[i] = '+';
                chars[i + 1] = '+';
                visited.put(new String(chars), result);
                if (result) return true;
            }
        }
        return false;
    }
}