488.祖玛游戏

https://leetcode-cn.com/problems/zuma-game/

dfs+剪枝+备忘录

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        board = list(board)
        hand = list(hand)
        memo = {}

        def dfs(board, hand):
            #递归出口，为区分桌上的球消完还是手里的球用完，返回不同的值
            if not board:
                return 0
            if not hand:
                return -1
            res = -1
            #遍历手里每个球
            for j,h in enumerate(hand):
                hand.pop(j)
                #遍历桌上n个球构成的n+1个空隙，尝试插入每一个
                for i in range(len(board) + 1):
                    #多个相同，插最右边
                    if i + 1 < len(board) and board[i] == board[i+1] == h:
                        continue
                    board_copy = board[0:i] + [h] + board[i:]

                    l,r = i,i
                    boom=True   #能否消消乐
                    # 连锁反应，直到不能再消除
                    while boom and l >=0 and r < len(board_copy) and board_copy[l] == board_copy[r]:
                        #左右扩散
                        while l > 0 and board_copy[l-1] == board_copy[l]:
                            l-=1
                        while r +1 < len(board_copy)  and board_copy[r+1] == board_copy[r]:
                            r += 1
                        if r-l+1 >= 3:  #连续超过三就开始连锁消消乐（初始情况不会有连续三个，但经过消消乐之后可能会出现三个或以上连续的）
                            board_copy = board_copy[:l] + board_copy[r+1:]
                            boom = True
                            l -= 1
                            r = l
                        else:
                            boom = False
                    #dfs回溯+备忘录
                    rec = (tuple(board_copy), tuple(hand))  #当前board和hand作为备忘录key
                    #备忘录有记录则直接返回，否则dfs递归
                    if rec in memo:
                        res_dfs = memo[rec]
                    else:
                        res_dfs = dfs(board_copy, hand)
                        memo[rec] = res_dfs     #得到新结果写备忘录

                    if res_dfs != -1:   #不是球用完了
                        if res == -1:
                            res = res_dfs
                        elif res_dfs < res:
                            res = res_dfs
                #恢复现场
                hand.insert(j,h)
            return  res+1 if res != -1 else -1
        return dfs(board, hand)