LeetCode 题解

LeetCode 第 1079 题：“活字印刷”题解

题解地址：回溯算法（Python 代码）。

说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。

传送门：1079. 活字印刷。

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

示例 1：

输入："AAB" 输出：8 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。 示例 2：

输入："AAABBC" 输出：188

提示：

1 <= tiles.length <= 7 tiles 由大写英文字母组成

回溯算法（Python 代码）

思路分析：

这道题与 LeetCode 第 90 题：子集 II很像，把 LeetCode 第 90 题的每一个解变成排列，就是这道题了。

方法：回溯算法

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

（温馨提示：下面的幻灯片中，有几页上有较多的文字，可能需要您停留一下，可以点击右下角的后退 “|◀” 或者前进 “▶|” 按钮控制幻灯片的播放。）

1079-1.png

1079-2.png

1079-3.png

1079-4.png

1079-5.png

1079-6.png

1079-7.png

1079-8.png

1079-9.png

1079-10.png

1079-11.png

1079-12.png

1079-13.png

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

参考代码：

Python 代码：

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

←