August 11, 2019

294. Flip Game II

Recursion (backtracking)

博弈类型题目。先手在当前可以选择的步骤中走一步，将新的状态传递给下一层递归。面对新的状态，判断后手是否会输，如果会输，那么就返回True，即先手能赢。注意只要有一种后手不会赢的情况就返回True。时间复杂度是指数。

参考链接： https://www.youtube.com/watch?v=rjOTv7dzqC8 https://zhuanlan.zhihu.com/p/20611132

class Solution {
        
    public boolean canWin(String s) {
        char[] array = s.toCharArray();
        return flipHelper(array);
    }
    
    private boolean flipHelper(char[] array) {
        
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] == '+' && array[i + 1] == '+') {
                array[i] = array[i + 1] = '-';
                boolean otherWin = flipHelper(array);
                array[i] = array[i + 1] = '+';
                
                // !otherWin 是判断对手失败的出口，对手失败了自己就赢了。
                if (!otherWin) {
                    return true;
                }
            }
        } 
        return false;
    }
}

Another solution:

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) == '+' && s.charAt(i + 1) == '+') {
                String next = s.substring(0, i) + "--" + s.substring(i + 2);
                if (!canWin(next)) {
                    return true;
                }
            }
        }
        return false;
    }
}

Optimize space complexity: recursion + memoization

class Solution {
        
    public boolean canWin(String s) {
        char[] array = s.toCharArray();
        Map<String, Boolean> map = new HashMap<>();
        return isWin(array, map);
    }
    
    private boolean isWin(char[] array, Map<String, Boolean> map) {
        
        String s = Arrays.toString(array);
        
        if (map.containsKey(s)) {
            return map.get(s);
        }
        
        boolean isWin = false;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] == '+' && array[i + 1] == '+') {
                array[i] = array[i + 1] = '-';
                boolean otherWin = isWin(array, map);
                array[i] = array[i + 1] = '+';
 
                // !otherWin 是判断对手失败的出口，对手失败了自己就赢了。
                if (!otherWin) {
                    isWin = true;
                    break;
                }
            }
        } 
        map.put(s, isWin);
        return isWin;
    }
}