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&& memo) { const string hashKey = board + '#' + hand; if (const auto it = memo.find(hashKey); it != memo.cend()) return it->second; board = deDup(board); if (board == "#") return 0; unordered_set boardSet = unordered_set(board.begin(), board.end()); string hs; // hand that is in board for (const char h : hand) if (boardSet.count(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(move(newBoard), newHand, move(memo)); if (res < INT_MAX) ans = min(ans, 1 + res); } return memo[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 memo = new HashMap<>(); final int ans = dfs(board + '#', hand, memo); return ans == Integer.MAX_VALUE ? -1 : ans; } private int dfs(String board, final String hand, Map memo) { final String hashKey = board + '#' + hand; if (memo.containsKey(hashKey)) return memo.get(hashKey); board = deDup(board); if (board.equals("#")) return 0; Set 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, memo); if (res < Integer.MAX_VALUE) ans = Math.min(ans, 1 + res); } memo.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