Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/488.html

488. Zuma Game

Level

Hard

Description

Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand.

Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed.

Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.

Example 1:

Input: board = “WRRBBW”, hand = “RB”

Output: -1

Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW

Example 2:

Input: board = “WWRRBBWW”, hand = “WRBRW”

Output: 2

Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

Example 3:

Input: board = “G”, hand = “GGGGG”

Output: 2

Explanation: G -> G[G] -> GG[G] -> empty

Example 4:

Input: board = “RBYYBBRRB”, hand = “YRBGB”

Output: 3

Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty

Constraints:

  • You may assume that the initial row of balls on the table wont have any 3 or more consecutive balls with the same color.
  • The number of balls on the table won’t exceed 16, and the string represents these balls is called “board” in the input.
  • The number of balls in your hand won’t exceed 5, and the string represents these balls is called “hand” in the input.
  • Both input strings will be non-empty and only contain characters ‘R’,’Y’,’B’,’G’,’W’.

Solution

Use backtrack with memorization. First loop over hand to obtain the number of balls of each color in hand. Then call the backtrack method.

In the backtrack method, first remove three or more consecutive balls with the same color from board. The remove operation is executed several times over board until no more balls can be removed. Then return 0 if board is empty. Use board concatenated with the string representation of each color’s count as the key to loop up the memorization. If the key exists, obtain the number of insertions from the key and return.

For each available color in hand, try each insertion position in board and obtain the minimum number of insertions, and update the memorization. If the empty string is reached, then it is possible to remove all the balls, and return the minimum number of insertions. Otherwise, return -1.

  • class Solution {
    public int findMinStep(String board, String hand) {
        Map<Character, Integer> colorIdMap = new HashMap<Character, Integer>();
        Map<Integer, Character> idColorMap = new HashMap<Integer, Character>();
        String colors = "RYBGW";
        for (int id = 0; id < 5; id++) {
            char color = colors.charAt(id);
            colorIdMap.put(color, id);
            idColorMap.put(id, color);
        }
        Map<String, Integer> memo = new HashMap<String, Integer>();
        int[] hands = new int[5];
        int handLength = hand.length();
        for (int i = 0; i < handLength; i++) {
            char c = hand.charAt(i);
            int index = colorIdMap.get(c);
            hands[index]++;
        }
        return backtrack(board, hands, idColorMap, memo);
    }

    public int backtrack(String board, int[] hands, Map<Integer, Character> idColorMap, Map<String, Integer> memo) {
        board = removeSame(board);
        if (board.length() == 0)
            return 0;
        String key = board + Arrays.toString(hands);
        if (memo.containsKey(key))
            return memo.get(key);
        int insertions = -1;
        int handsLength = hands.length, boardLength = board.length();
        for (int i = 0; i < handsLength; i++) {
            if (hands[i] != 0) {
                char color = idColorMap.get(i);
                hands[i]--;
                for (int j = 0; j <= boardLength; j++) {
                    String newBoard = board.substring(0, j) + color + board.substring(j);
                    int nextInsertions = backtrack(newBoard, hands, idColorMap, memo);
                    if (nextInsertions != -1) {
                        if (insertions == -1)
                            insertions = nextInsertions + 1;
                        else
                            insertions = Math.min(insertions, nextInsertions + 1);
                    }
                }
                hands[i]++;
            }
        }
        memo.put(key, insertions);
        return insertions;
    }

    public String removeSame(String board) {
        StringBuffer sb = new StringBuffer(board);
        int length = sb.length();
        boolean flag = true;
        while (flag) {
            int left = length - 2, right = length - 1;
            while (left >= 0) {
                if (sb.charAt(left) == sb.charAt(right))
                    left--;
                else {
                    if (right - left >= 3) {
                        sb.delete(left + 1, right + 1);
                        right = left;
                        left--;
                    } else
                        right = left;
                }
            }
            if (right - left >= 3)
                sb.delete(left + 1, right + 1);
            int curLength = sb.length();
            if (curLength == length)
                flag = false;
            else
                length = curLength;
        }
        return sb.toString();
    }
}

  • class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        def remove(s):
            while len(s):
                next = re.sub(r'B{3,}|G{3,}|R{3,}|W{3,}|Y{3,}', '', s)
                if len(next) == len(s):
                    break
                s = next
            return s

        visited = set()
        q = deque([(board, hand)])
        while q:
            state, balls = q.popleft()
            if not state:
                return len(hand) - len(balls)
            for ball in set(balls):
                b = balls.replace(ball, '', 1)
                for i in range(1, len(state) + 1):
                    s = state[:i] + ball + state[i:]
                    s = remove(s)
                    if s not in visited:
                        visited.add(s)
                        q.append((s, b))
        return -1

############

class Solution(object):
  def findMinStep(self, board, hand):
    """
    :type board: str
    :type hand: str
    :rtype: int
    """

    def dfs(line, balls, visited):
      line = reduceLine(line)
      if (line, balls) in visited:
        return visited[line, balls]
      if len(line) == 0:
        return len(hand) - len(balls)
      if len(balls) == 0:
        return float("inf")
      res = float("inf")
      for i in range(len(balls)):
        for j in range(len(line) + 1):
          if j == 0 and line[0] != balls[i]:
            continue
          elif j == len(line) and line[-1] != balls[i]:
            continue
          elif 0 < j < len(line) and balls[i] != line[j - 1] and balls[i] != line[j]:
            continue
          res = min(res, dfs(line[:j] + balls[i] + line[j:], balls[:i] + balls[i + 1:], visited))
      visited[line, balls] = res
      return res

    def reduceLine(line):
      def reducer(line):
        if len(line) < 3:
          return line
        ret = []
        dp = [1] * len(line)
        pre = line[-1]
        count = 1
        for i in reversed(range(len(line) - 1)):
          if line[i] == pre:
            count += 1
          else:
            pre = line[i]
            count = 1
          dp[i] = count
        i = 0

        while i < len(line):
          if dp[i] >= 3:
            i += dp[i]
          else:
            ret.extend(line[i:i + dp[i]])
            i += dp[i]
        return "".join(ret)

      if len(line) < 3:
        return line
      ans = line
      for _ in range(len(line) / 3):
        ans = reducer(ans)
      return ans

    visited = {}
    ret = dfs(board, "".join(sorted(hand)), visited)
    return ret if ret != float("inf") else -1

All Problems

All Solutions