LeetCode Solutions

			

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>&& memo) {
    const string& hashKey = board + '#' + hand;
    if (memo.count(hashKey))
      return memo[hashKey];
    board = deDup(board);
    if (board == "#")
      return 0;

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

    string hs;  // Hand that 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;  // 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;
  }
};

			

class Solution {
  public int findMinStep(String board, String hand) {
    Map<String, Integer> 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<String, Integer> memo) {
    final String hashKey = board + '#' + hand;
    if (memo.containsKey(hashKey))
      return memo.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, 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; // 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;
  }
}

			

class Solution:
  def findMinStep(self, board: str, hand: str) -> int:
    def deDup(board):
      start = 0  # 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 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