Leetcode Zuma Game problem solution

In this Leetcode Zuma Game problem solution You are playing a variation of the game Zuma.

In this variation of Zuma, there is a single row of colored balls on a board, where each ball can be colored red 'R', yellow 'Y', blue 'B', green 'G', or white 'W'. You also have several colored balls in your hand.

Your goal is to clear all of the balls from the board. On each turn:

Pick any ball from your hand and insert it in between two balls in the row or on either end of the row.

If there is a group of three or more consecutive balls of the same color, remove the group of balls from the board.

If this removal causes more groups of three or more of the same color to form, then continue removing each group until there are none left.

If there are no more balls on the board, then you win the game.

Repeat this process until you either win or do not have any more balls in your hand.

Given a string board, representing the row of balls on the board, and a string hand, representing the balls in your hand, return the minimum number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return -1.

Problem solution in Python.

def insert(self, board, pos=-1, new=-1):
    if pos >= 0:
        board.insert(pos, new)
    stack = []
    for c in board + ['&']:
        if len(stack) >= 3 and c != stack[-1] and stack[-3] == stack[-2] == stack[-1]:
            to_remove = stack[-1]
            while stack and stack[-1] == to_remove:
                stack.pop()
        stack.append(c)
    return stack[:-1]

def dfs(self, board, hid, hand):
    ans = float('inf')
    if hid < len(hand) - 1:
        ans = self.dfs(board, hid+1, hand)
    for i in range(len(board)+1):
        board_dup = list(board)
        board_dup = self.insert(board_dup, i, hand[hid])
        if not board_dup:
            return 1
        if hid < len(hand) - 1:
            ans = min(ans, self.dfs(board_dup, hid+1, hand)+1)
    return ans

def findMinStep(self, board: str, hand: str) -> int:
    ans = self.dfs([*board], 0, [*hand])
    return ans if ans != float('inf') else -1

Problem solution in Java.

public int findMinStep(String board, String hand) {
    Map<Character, Integer> mp = new HashMap<>();
    for(int i = 0; i < hand.length(); i++){
        char c = hand.charAt(i);
        mp.put(c, mp.getOrDefault(c, 0) + 1);
    }
    return dfs(board, mp);
}

public int dfs(String board, Map<Character, Integer> mp){
    board = truncate(board);
    if(board.length() < 1) return 0;
    if(board.length() == 1 && mp.containsKey(board.charAt(0)) && mp.get(board.charAt(0)) >= 2) return 2;
    int min = Integer.MAX_VALUE;
    for(int i = 0, j = 1; j < board.length(); j++){
        char a = board.charAt(i);
        while(j < board.length() && a == board.charAt(j)) j++;
        if(mp.containsKey(a) && mp.get(a) >= 3 - (j - i)){
            int values = mp.get(a);
            int substract = 3 - (j - i);
            mp.put(a, values - substract);
            int number = dfs(board.substring(0, i) + board.substring(j), mp);
            i = j;
            if(number != -1) min = Math.min(min, substract + number);
            mp.put(a, values);
        }
        i = j;
    }
    return min == Integer.MAX_VALUE ? -1 : min;
}

public String truncate(String board){
    for(int i = 0, j = 1; j < board.length(); j++){
        while(j < board.length() && board.charAt(j) == board.charAt(i)){
            j++;
        }
        if(j - i >= 3) board = truncate(board.substring(0, i)  + board.substring(j));
        i = j;
    }
    return board;
}

Problem solution in C++.

class Solution {
public:
    int findMinStep(string board, string hand) {
        board = removeAllBalls(board);
        if (board.empty()) {
            return 0;
        }
        int res = INT_MAX;
        unordered_multimap<string, string> cache;
        dfs(board, hand, res, 0, cache);
        return (res == INT_MAX) ? -1 : res;
    }
    
    void dfs(string& board, string& hand, int& res, int balls, unordered_multimap<string, string>& cache) {
        if (cache.find(board) != cache.end() && cache.find(board)->second == hand) {
            return;
        }
        if (board.empty()) {
            res = min(res, balls);
            return;
        }
        if (hand.empty()) {
            return;
        }
        for (int i=0; i<hand.size(); i++) {
            char ch = hand[i];
            hand.erase(i, 1);
            for (int j=0; j<=board.size(); j++) {
                board.insert(j, 1, ch);
                string tmp = removeAllBalls(board);
                dfs(tmp, hand, res, balls+1, cache);
                cache.insert(make_pair(tmp, hand));
                board.erase(j, 1);
            }
            hand.insert(i, 1, ch);
        }
    }
    
    string removeAllBalls(string board) {
        string res = update(board);
        while (res != board) {
            board = res;
            res = update(board);
        }
        return res;
    }
    
    string update(string s) {
        string res = "";
        int l = 0, r = 0;
        while (r < s.size()) {
            r++;
            if (s[r] != s[l]) {
                if (r - l < 3) {
                    for (int i=l; i<r; i++) {
                        res += s[i];
                    }
                }
                l = r;
            }
        }
        if (l - r < 3) {
            for (int i=l; i<r; i++) {
                res += s[i];
            }
        }
        return res;
    }
};