488.md

488 Zuma Game

Description

link

---

Solution

定义DFS的输入输出至关重要，实际上这题是hashmap+dfs

这里讲一下DFS的时间复杂度判断：如果是最坏情况的话，首先因为初始DFS的循环是O(M + N)，每个点的最大遍历长度是O(MN)，这就是最坏情况的时间复杂度

---

Code

最坏情况下是O(n^2)

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        def dfs(s, cnt):
            if not s: return 0
            res = float("inf")
            i = 0
            while i < len(s):
                j = i + 1
                while j < len(s) and s[j] == s[i]:
                    j += 1
                same_len = j - i
                lack = 3 - same_len
                lack = 0 if lack < 0 else lack
                if cnt[s[i]] >= lack:
                    cnt[s[i]] -= lack
                    tmp = dfs(s[:i] + s[j:], cnt)
                    if tmp >= 0:
                        res = min(res, lack + tmp)
                    cnt[s[i]] += lack
                i = j
            return res if res != float("inf") else -1
        return dfs(board, collections.Counter(hand))