golang 刷leetcode：祖玛游戏

你正在参与祖玛游戏的一个变种。

在这个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W' 。你的手中也有一些彩球。

你的目标是 清空 桌面上所有的球。每一回合：

从你手上的彩球中选出 任意一颗 ，然后将其插入桌面上那一排球中：两球之间或这一排球的任一端。

接着，如果有出现 三个或者三个以上 且 颜色相同 的球相连的话，就把它们移除掉。

如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则可以继续移除这些球，直到不再满足移除条件。

如果桌面上所有球都被移除，则认为你赢得本场游戏。

重复这个过程，直到你赢了游戏或者手中没有更多的球。

给你一个字符串 board ，表示桌面上最开始的那排球。另给你一个字符串 hand ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 最少 球数。如果不能移除桌上所有的球，返回 -1 。

示例 1：

输入：board = "WRRBBW", hand = "RB"

输出：-1

解释：无法移除桌面上的所有球。可以得到的最好局面是：

- 插入一个 'R' ，使桌面变为 WRRRBBW 。WRRRBBW -> WBBW

- 插入一个 'B' ，使桌面变为 WBBBW 。WBBBW -> WW

桌面上还剩着球，没有其他球可以插入。

示例 2：

输入：board = "WWRRBBWW", hand = "WRBRW"

输出：2

解释：要想清空桌面上的球，可以按下述步骤：

- 插入一个 'R' ，使桌面变为 WWRRRBBWW 。WWRRRBBWW -> WWBBWW

- 插入一个 'B' ，使桌面变为 WWBBBWW 。WWBBBWW -> WWWW -> empty

只需从手中出 2 个球就可以清空桌面。

示例 3：

输入：board = "G", hand = "GGGGG"

输出：2

解释：要想清空桌面上的球，可以按下述步骤：

- 插入一个 'G' ，使桌面变为 GG 。

- 插入一个 'G' ，使桌面变为 GGG 。GGG -> empty

只需从手中出 2 个球就可以清空桌面。

示例 4：

输入：board = "RBYYBBRRB", hand = "YRBGB"

输出：3

解释：要想清空桌面上的球，可以按下述步骤：

- 插入一个 'Y' ，使桌面变为 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B

- 插入一个 'B' ，使桌面变为 BB 。

- 插入一个 'B' ，使桌面变为 BBB 。BBB -> empty

只需从手中出 3 个球就可以清空桌面。

提示：

1 <= board.length <= 16

1 <= hand.length <= 5

board 和 hand 由字符 'R'、'Y'、'B'、'G' 和 'W' 组成

桌面上一开始的球中，不会有三个及三个以上颜色相同且连着的球

解题思路：

对于这种需要排列组合的题目很多时候都是回溯法加剪枝的思路

1，如何消除？如果连续，就把连续的去除掉，然后将剩余部分拼接，递归消除。

2，如何回溯？

A：完成条件：判断消除后board长度是不是0，如果是就满足完成条件

B：中断条件：如果以前算过这个分支，可以中断返回

C：循环递归

D：记忆化保存

3，如何循环递归？

A，for 循环遍历board和hand

B，选择hand插入board

C，递归消除

D，递归计算

E，计算score

F，回溯：恢复board和hand

const MAXSCORE=6
func findMinStep(board string, hand string) int {
    m:=make(map[string]int)
    if backtrack(board, hand,m) == MAXSCORE{
         return -1
    }
    return m[board+ "," + hand]
}

func backtrack(board,hand string,m map[string]int)int{
    //完成条件
    if len(recur(board))==0{
        return 0
    }
    //中断条件
    score := MAXSCORE
    status := board + "," + hand
    if v,ok:=m[status];ok{
        return v
    } 
        //for循环
            //选择
//                递归消除
            //回溯
            //撤销选择
        for i := 0; i < len(hand); i++ {
            for j := 0; j < len(board); j++ {
                board=board[:j]+string([]byte{hand[i]})+board[j:]
                
                boardNew:=recur(board)
                if len(boardNew)==0{
                   m[status]=1
               
                  if j==len(board)-1{
                        board=board[:j]
                    }else{
                        board=board[:j]+board[j+1:]
                   }  
                   return 1
                }
                
                if i==len(hand)-1{
                     hand=hand[:i]
                }else{
                     hand=hand[:i]+hand[i+1:]
                }

                score = min(score, backtrack(boardNew,hand,m) + 1)
               
               //恢复
                hand=hand[:i]+string([]byte{board[j]})+hand[i:]
                if j==len(board)-1{
                     board=board[:j]
                }else{
                     board=board[:j]+board[j+1:]
                }
            }
        }
        //记忆化保存
      m[status]=score
    return score
}

func min(a, b int)int{
    if a<b{
        return a
    }
    return b
}

//递归消除
func recur(board string)string{
    i:=0
    j:=0
    for ;j<=len(board);j++{
        if j<len(board) &&board[i]==board[j]{
            continue
        }
        if j-i>2{
           return recur(board[0:i]+ board[j:])
        }
        i=j
    }
    return board
}

复制

剪枝条件：

• 第 11 个剪枝条件：手中颜色相同的球每次选择时只需要考虑其中一个即可
• 第 22 个剪枝条件：只在连续相同颜色的球的开头位置或者结尾位置插入新的颜色相同的球
• 第 23 个剪枝条件：只考虑放置新球后有可能得到更优解的位置：
• 插入新球与插入位置右侧的球颜色相同；
• 插入新球与插入位置两侧的球颜色均不相同，且插入位置两侧的球的颜色不同；
• 插入新球与插入位置两侧的球颜色均不相同，且插入位置两侧的球的颜色相同。 只有第一种情况可能有最优解