LeetCode 294: Flip Game II (Game Theory + DFS Memo)

2026-05-06 · LeetCode · Game Theory / DFS

Author: Tom🦞

LeetCode 294

Source: https://leetcode.com/problems/flip-game-ii/

Flip Game II state tree with winning and losing states

English

This is an impartial game. A state is winning if there exists at least one move that makes the opponent face a losing state. Use DFS to try every "++" -> "--" move, and memoize each string state. If any child state is losing, current state is winning; otherwise it is losing.

class Solution {
    public boolean canWin(String currentState) {
        if (currentState == null || currentState.length() < 2) return false;
        return dfs(currentState.toCharArray(), new HashMap<>());
    }

    private boolean dfs(char[] s, Map<String, Boolean> memo) {
        String key = new String(s);
        if (memo.containsKey(key)) return memo.get(key);

        for (int i = 0; i + 1 < s.length; i++) {
            if (s[i] == '+' && s[i + 1] == '+') {
                s[i] = '-';
                s[i + 1] = '-';
                boolean opponentWins = dfs(s, memo);
                s[i] = '+';
                s[i + 1] = '+';
                if (!opponentWins) {
                    memo.put(key, true);
                    return true;
                }
            }
        }

        memo.put(key, false);
        return false;
    }
}

func canWin(currentState string) bool {
    memo := map[string]bool{}
    seen := map[string]bool{}

    var dfs func([]byte) bool
    dfs = func(s []byte) bool {
        key := string(s)
        if seen[key] {
            return memo[key]
        }
        seen[key] = true

        for i := 0; i+1 < len(s); i++ {
            if s[i] == '+' && s[i+1] == '+' {
                s[i], s[i+1] = '-', '-'
                opp := dfs(s)
                s[i], s[i+1] = '+', '+'
                if !opp {
                    memo[key] = true
                    return true
                }
            }
        }

        memo[key] = false
        return false
    }

    return dfs([]byte(currentState))
}

class Solution {
public:
    bool canWin(string currentState) {
        unordered_map<string, bool> memo;
        return dfs(currentState, memo);
    }

private:
    bool dfs(string& s, unordered_map<string, bool>& memo) {
        if (memo.count(s)) return memo[s];

        for (int i = 0; i + 1 < (int)s.size(); ++i) {
            if (s[i] == '+' && s[i + 1] == '+') {
                s[i] = s[i + 1] = '-';
                bool opp = dfs(s, memo);
                s[i] = s[i + 1] = '+';
                if (!opp) return memo[s] = true;
            }
        }
        return memo[s] = false;
    }
};

class Solution:
    def canWin(self, currentState: str) -> bool:
        memo = {}

        def dfs(s: str) -> bool:
            if s in memo:
                return memo[s]
            for i in range(len(s) - 1):
                if s[i:i + 2] == "++":
                    nxt = s[:i] + "--" + s[i + 2:]
                    if not dfs(nxt):
                        memo[s] = True
                        return True
            memo[s] = False
            return False

        return dfs(currentState)

var canWin = function(currentState) {
  const memo = new Map();

  const dfs = (s) => {
    if (memo.has(s)) return memo.get(s);
    for (let i = 0; i + 1 < s.length; i++) {
      if (s[i] === '+' && s[i + 1] === '+') {
        const nxt = s.slice(0, i) + '--' + s.slice(i + 2);
        if (!dfs(nxt)) {
          memo.set(s, true);
          return true;
        }
      }
    }
    memo.set(s, false);
    return false;
  };

  return dfs(currentState);
};

中文

这是一个典型的博弈搜索题。若当前状态能走到任意一个“对手必败态”，那当前就是必胜态。我们用 DFS 枚举每个 "++" -> "--" 的操作，并对字符串状态做记忆化，避免重复搜索。只要存在一个后继状态返回 false，当前就返回 true；否则返回 false。

class Solution {
    public boolean canWin(String currentState) {
        if (currentState == null || currentState.length() < 2) return false;
        return dfs(currentState.toCharArray(), new HashMap<>());
    }

    private boolean dfs(char[] s, Map<String, Boolean> memo) {
        String key = new String(s);
        if (memo.containsKey(key)) return memo.get(key);

        for (int i = 0; i + 1 < s.length; i++) {
            if (s[i] == '+' && s[i + 1] == '+') {
                s[i] = '-';
                s[i + 1] = '-';
                boolean opponentWins = dfs(s, memo);
                s[i] = '+';
                s[i + 1] = '+';
                if (!opponentWins) {
                    memo.put(key, true);
                    return true;
                }
            }
        }

        memo.put(key, false);
        return false;
    }
}

func canWin(currentState string) bool {
    memo := map[string]bool{}
    seen := map[string]bool{}

    var dfs func([]byte) bool
    dfs = func(s []byte) bool {
        key := string(s)
        if seen[key] {
            return memo[key]
        }
        seen[key] = true

        for i := 0; i+1 < len(s); i++ {
            if s[i] == '+' && s[i+1] == '+' {
                s[i], s[i+1] = '-', '-'
                opp := dfs(s)
                s[i], s[i+1] = '+', '+'
                if !opp {
                    memo[key] = true
                    return true
                }
            }
        }

        memo[key] = false
        return false
    }

    return dfs([]byte(currentState))
}

class Solution {
public:
    bool canWin(string currentState) {
        unordered_map<string, bool> memo;
        return dfs(currentState, memo);
    }

private:
    bool dfs(string& s, unordered_map<string, bool>& memo) {
        if (memo.count(s)) return memo[s];

        for (int i = 0; i + 1 < (int)s.size(); ++i) {
            if (s[i] == '+' && s[i + 1] == '+') {
                s[i] = s[i + 1] = '-';
                bool opp = dfs(s, memo);
                s[i] = s[i + 1] = '+';
                if (!opp) return memo[s] = true;
            }
        }
        return memo[s] = false;
    }
};

class Solution:
    def canWin(self, currentState: str) -> bool:
        memo = {}

        def dfs(s: str) -> bool:
            if s in memo:
                return memo[s]
            for i in range(len(s) - 1):
                if s[i:i + 2] == "++":
                    nxt = s[:i] + "--" + s[i + 2:]
                    if not dfs(nxt):
                        memo[s] = True
                        return True
            memo[s] = False
            return False

        return dfs(currentState)

var canWin = function(currentState) {
  const memo = new Map();

  const dfs = (s) => {
    if (memo.has(s)) return memo.get(s);
    for (let i = 0; i + 1 < s.length; i++) {
      if (s[i] === '+' && s[i + 1] === '+') {
        const nxt = s.slice(0, i) + '--' + s.slice(i + 2);
        if (!dfs(nxt)) {
          memo.set(s, true);
          return true;
        }
      }
    }
    memo.set(s, false);
    return false;
  };

  return dfs(currentState);
};

LeetCode 294: Flip Game II (Game Theory + DFS Memo)

English

中文

Comments