0°

LeetCode 第 1079 题:活字印刷

说明:本文是根据自己在 LeetCode 中文网站上发布的题解写成的,即自己转载了自己的文章。
原文地址:
https://leetcode-cn.com/problems/letter-tile-possibilities/solution/hui-su-suan-fa-python-dai-ma-by-liweiwei1419/

这道题与 LeetCode 第 90 题很像,把 LeetCode 第 90 题的每一个解变成排列,就是这道题了。

由于是排列,我们不难想到,解决这个问题的思路应该是一个树形结构。不妨先从规模小的问题入手,以题目示例 1 的输入:“AAB”为例,可以画出树形图如下。


image.png

我们只要一开始做一个字母频次统计,如果当前这个字母的频次为 0,就不再往下执行,马上要回溯了,在回溯的过程中一定要记得状态重置。

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        counter = [0] * 26
        for alpha in tiles:
            counter[ord(alpha) - ord('A')] += 1
        return self.__dfs(counter)
    def __dfs(self, counter):
        res = 0
        for i in range(26):
            if counter[i] == 0:
                continue
            res += 1
            counter[i] -= 1
            res += self.__dfs(counter)
            counter[i] += 1
        return res

饥饿鲨:进化下载
「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!