其实本题并不是很难，只是我觉得这个方法太傻了就没用，后来看了讨论，感觉这个方法在面试中也是可行的，就决定直接用recursive。但是在这个基础上加了memorization里记录必赢和必输的String

    • 时间复杂度：
      • 最开始有294. Flip Game II - 图1种组合
      • 当第一层设定好之后，根据位置的不同，最多会有294. Flip Game II - 图2种可能性，当然也可能更少
      • 所以时间复杂度是294. Flip Game II - 图3
      • 也被称作Double Factorial

    代码:

    1. class Solution {
    3.   public boolean canWin(String s) {
    4.     Set<String> winSet = new HashSet<>();
    5.     Set<String> loseSet = new HashSet<>();
    7.     return helper(s, winSet, loseSet);
    8.   }
    10.   private boolean helper(String s, Set<String> winSet, Set<String> loseSet) {
    11.     if (winSet.contains(s)) {
    12.       return true;
    13.     }
    14.     if (loseSet.contains(s)) {
    15.       return false;
    16.     }
    17.     for (int i = 0; i < s.length() - 1; ++i) {
    18.       if (s.charAt(i) == '+' && s.charAt(i+1) == '+') {
    19.         String newS = s.substring(0, i) + "--" + s.substring(i+2);
    20.         if (!helper(newS, winSet, loseSet)) {
    21.           winSet.add(s);
    22.           return true;
    23.         }
    24.       }
    25.     }
    26.     loseSet.add(s);
    27.     return false;
    28.   }
    29. }