488. Zuma game

You are participating in a variant of Zuma game.

In this Zuma game variant, there is a row of colored balls on the table. The color of each ball may be red 'R', yellow 'Y', blue 'B', green 'G' or white 'W'. You also have some colored balls in your hand.

Your goal is to empty all the balls on the table. Each round:
Choose any one of the colored balls in your hand and insert it into the volleyball on the table: between the two balls or at either end of the volleyball.
Then, if there are three or more balls of the same color connected, remove them.
If this removal operation also causes three or more balls of the same color to be connected, you can continue to remove these balls until the removal conditions are no longer met.
If all the balls on the table are removed, you are considered to have won the game.
Repeat this process until you win the game or have no more balls in your hand.
Give you a string board, which represents the volleyball at the beginning on the desktop. Another string hand is given to you to represent the colored ball in your hand. Please follow the above steps to remove all the balls on the table, calculate and return the minimum number of balls required. If you cannot remove all the balls on the table, return - 1.
1 <= board.length <= 16
1 <= hand.length <= 5
board and hand consist of the characters' R ',' Y ',' B ',' G 'and' W '
There will not be three or more balls with the same color and connected at the beginning of the ball on the desktop

Example 1:

Input: board = "WRRBBW", hand = "RB"
Output: - 1
Explanation: you cannot remove all balls from the desktop. The best situation available is:
·Insert an 'R' to change the desktop to wrrrbbw. WRRRBBW -> WBBW
·Insert a 'B' to make the desktop wbbbw. WBBBW -> WW
There are balls left on the table. No other balls can be inserted.

Example 2:

Input: board = "WWRRBBWW", hand = "WRBRW"
Output: 2
Explanation: to empty the ball on the desktop, follow the steps below:
·Insert an 'R' to change the desktop to wwrrrbbww. WWRRRBBWW -> WWBBWW
·Insert a 'B' to change the desktop to wwbbbww. WWBBBWW -> WWWW -> empty
Just take 2 balls out of your hand to empty the desktop.

Example 3:

Input: board = "G", hand = "gggggg"
Output: 2
Explanation: to empty the ball on the desktop, follow the steps below:
·Insert a 'G' to change the desktop to GG.
·Insert a 'G' to change the desktop to GGG. GGG -> empty
Just take 2 balls out of your hand to empty the desktop.

Example 4:

Input: board = "RBYYBBRRB", hand = "YRBGB"
Output: 3
Explanation: to empty the ball on the desktop, follow the steps below:
·Insert a 'Y' to change the desktop to rbyybbrrb. RBYYYBBRRB -> RBBBRRB -> RRRB -> B
·Insert a 'B' to make the desktop BB.
·Insert a 'B' to make the desktop BBB. BBB -> empty
Just three balls from your hand can empty the desktop.

code:

class Solution {
	final int MAXSCORE = 6;
	Map<String, Integer> map = new HashMap<>();
	public int findMinStep(String board, String hand) {
		if (backtrack(new StringBuilder(board), new StringBuilder(hand)) == MAXSCORE)
			return -1;
		return map.get(board + "," + hand);
	}
	private int backtrack(StringBuilder board, StringBuilder hand) {
		int score = MAXSCORE;
		if (board.length() == 0)
			return score;
		String status = board + "," + hand;
		if (map.containsKey(status))
			return map.get(status);
		for (int i = 0; i < hand.length(); i++) {
			for (int j = 0; j < board.length(); j++) {
				board.insert(j, hand.charAt(i));
				String newBoard = recur(board.toString());
				if (newBoard.length() == 0) {
					map.put(status, 1);
					return 1;
				}
				hand.deleteCharAt(i);
				score = Math.min(score, backtrack(new StringBuilder(newBoard), hand) + 1);
				hand.insert(i, board.charAt(j));
				board.deleteCharAt(j);
			}
		}
		map.put(status, score);
		return score;
	}
	String recur(String board) {
		int len = board.length();
		for (int l = 0, r = 0; r <= len; r++) {
			if (r < len && board.charAt(l) == board.charAt(r))
				continue;
			if (r - l > 2)
				return recur(board.substring(0, l) + board.substring(r));
			else
				l = r;
		}
		return board;
	}
}

Execution results:

Conclusion: on the 14th day of LeetCode punch in, you can see your shortcomings, improve your ability and make progress slowly in doing questions every day, but your code programming ability needs to be improved and you need to continue to refuel!