Skip to content

488. Zuma Game 👎

  • Time: $O(m^2n^2)$, where $m = |\texttt{board}|$ and $n = |\texttt{hand}|$
  • Space: $O(m^2n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
 public:
  int findMinStep(string board, string hand) {
    const int ans = dfs(board + "#", hand, {});
    return ans == INT_MAX ? -1 : ans;
  }

 private:
  int dfs(string&& board, const string& hand,
          unordered_map<string, int>&& mem) {
    const string hashKey = board + '#' + hand;
    if (const auto it = mem.find(hashKey); it != mem.cend())
      return it->second;
    board = deDup(board);
    if (board == "#")
      return 0;

    unordered_set<char> boardSet = unordered_set(board.begin(), board.end());

    string hs;  // hand that is in board
    for (const char h : hand)
      if (boardSet.contains(h))
        hs += h;
    if (hs.empty())  // infeasible
      return INT_MAX;

    int ans = INT_MAX;

    for (int i = 0; i < board.size(); ++i)
      for (int j = 0; j < hs.size(); ++j) {
        // Place hs[j] in board[i].
        const string& newHand = hs.substr(0, j) + hs.substr(j + 1);
        string newBoard = board.substr(0, i) + hs[j] + board.substr(i);
        const int res = dfs(std::move(newBoard), newHand, std::move(mem));
        if (res < INT_MAX)
          ans = min(ans, 1 + res);
      }

    return mem[hashKey] = ans;
  }

  string deDup(string board) {
    int start = 0;  // the start index of a color sequenece
    for (int i = 0; i < board.size(); ++i)
      if (board[i] != board[start]) {
        if (i - start >= 3)
          return deDup(board.substr(0, start) + board.substr(i));
        start = i;  // Meet a new sequence.
      }
    return board;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
  public int findMinStep(String board, String hand) {
    Map<String, Integer> mem = new HashMap<>();
    final int ans = dfs(board + '#', hand, mem);
    return ans == Integer.MAX_VALUE ? -1 : ans;
  }

  private int dfs(String board, final String hand, Map<String, Integer> mem) {
    final String hashKey = board + '#' + hand;
    if (mem.containsKey(hashKey))
      return mem.get(hashKey);
    board = deDup(board);
    if (board.equals("#"))
      return 0;

    Set<Character> boardSet = new HashSet<>();
    for (final char c : board.toCharArray())
      boardSet.add(c);

    StringBuilder sb = new StringBuilder();
    for (final char h : hand.toCharArray())
      if (boardSet.contains(h))
        sb.append(h);
    final String hs = sb.toString();
    if (sb.length() == 0) // infeasible
      return Integer.MAX_VALUE;

    int ans = Integer.MAX_VALUE;

    for (int i = 0; i < board.length(); ++i)
      for (int j = 0; j < hs.length(); ++j) {
        // Place hs[j] in board[i].
        final String newHand = hs.substring(0, j) + hs.substring(j + 1);
        String newBoard = board.substring(0, i) + hs.charAt(j) + board.substring(i);
        final int res = dfs(newBoard, newHand, mem);
        if (res < Integer.MAX_VALUE)
          ans = Math.min(ans, 1 + res);
      }

    mem.put(hashKey, ans);
    return ans;
  }

  private String deDup(String board) {
    int start = 0; // the start index of a color sequenece
    for (int i = 0; i < board.length(); ++i)
      if (board.charAt(i) != board.charAt(start)) {
        if (i - start >= 3)
          return deDup(board.substring(0, start) + board.substring(i));
        start = i; // Meet a new sequence.
      }
    return board;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
  def findMinStep(self, board: str, hand: str) -> int:
    def deDup(board):
      start = 0  # the start index of a color sequenece
      for i, c in enumerate(board):
        if c != board[start]:
          if i - start >= 3:
            return deDup(board[:start] + board[i:])
          start = i  # Meet a new sequence.
      return board

    @functools.lru_cache(None)
    def dfs(board: str, hand: str):
      board = deDup(board)
      if board == '#':
        return 0

      boardSet = set(board)
      # hand that is in board
      hand = ''.join(h for h in hand if h in boardSet)
      if not hand:  # infeasible
        return math.inf

      ans = math.inf

      for i in range(len(board)):
        for j, h in enumerate(hand):
          # Place hs[j] in board[i].
          newHand = hand[:j] + hand[j + 1:]
          newBoard = board[:i] + h + board[i:]
          ans = min(ans, 1 + dfs(newBoard, newHand))

      return ans

    ans = dfs(board + '#', hand)
    return -1 if ans == math.inf else ans