「力扣」第 1079 题：活字印刷

• 题目链接：1079. 活字印刷 (opens new window)；
• 题解链接：回溯算法（设计递归函数的返回值） (opens new window)。

题目描述

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

**注意：**本题中，每个活字字模只能使用一次。

示例 1：

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

示例 2：

输入："AAABBC"
输出：188

提示：

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

思路分析

• 这道题与「力扣」第 90 题 （子集 II (opens new window)）很像，区别在于第 90 题的每一个解不强调顺序，而当前问题每一个解强调顺序，不同顺序构成了一个解。即：第 90 题是一个组合问题，当前问题是一个排列问题；
• 输入字符串还有多少字符可用是我们关注的，因此需要得到输入字符串的字符 频数 数组。题目最后说：「tiles 由大写英文字母组成」，因此可以使用长度为 26 的整型数组表示字符频数数组。

方法：回溯算法

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

这里有个动画，要到 力扣 (opens new window) 上看。

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

编码细节：

• 递归终止条件是：所有的字符都使用完毕。递归终止条件隐含在递归方法中；
• 递归函数的返回值的含义：以当前字符频数数组 count 能够产生的排列的总数。

参考代码：

Java 代码：

public class Solution {

    public int numTilePossibilities(String tiles) {
        int[] count = new int[26];
        char[] charArray = tiles.toCharArray();
        for (char c : charArray) {
            count[c - 'A']++;
        }
        // tiles 里所有的信息都存在 count 里，对 count 执行深度优先遍历即可
        return dfs(count);
    }

    /**
     * 设计递归函数的返回值
     *
     * @return 在当前的频数数组下，可以产生的排列数
     */
    private int dfs(int[] count) {
        // 递归终止条件是：当前没有可以用的字符（没有显示递归终止条件）
        int res = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] == 0) {
                continue;
            }
            res++;
            count[i]--;

            res += dfs(count);
            // 只需要重置字符频数数组
            count[i]++;
        }
        return res;
    }
}

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

---

作者：liweiwei1419 链接：https://suanfa8.com/tree/solutions/1079-letter-tile-possibilities 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。