1079. 活字印刷

🟠   🔖  哈希表 字符串 回溯 计数  🔗 力扣 LeetCode

题目

You have n tiles, where each tile has one letter tiles[i] printed on it.

Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

Example 1:

Input: tiles = "AAB"

Output: 8

Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"

Output: 188

Example 3:

Input: tiles = "V"

Output: 1

Constraints:

• 1 <= tiles.length <= 7
• tiles consists of uppercase English letters.

题目大意

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

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

示例 1：

输入： "AAB"

输出： 8

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

示例 2：

输入： "AAABBC"

输出： 188

示例 3：

输入： "V"

输出： 1

提示：

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

解题思路

本题的目标是计算出 tiles 中所有可能的排列数，包括长度不同的排列。由于 tiles 可能包含重复字符，直接使用全排列的方式会导致重复计算，因此采用回溯 + 计数数组的方式。

1. 预处理字符频次

由于 tiles 只包含大写英文字母（A-Z），我们可以使用长度为 26 的数组 count 来记录每个字符的出现次数：

• 例如 tiles = "AAB"，那么 count = [2, 1, 0, 0, ..., 0]。

2. 回溯生成排列

递归函数 backtrack(count) 负责构造所有可能的排列：

1. 遍历 26 个字母，如果 count[i] > 0，表示该字母可以使用：
   • 选择该字母，将其 count[i]--（标记已使用）。
   • 递归调用 backtrack(count) 计算当前状态下的所有可能排列数。
   • 递归返回后，将 count[i]++ 复原，进行下一次尝试（回溯）。
2. 每次选择一个字母都会生成一个新的排列，因此 total += 1 + backtrack(count)。

复杂度分析

• 时间复杂度：O(n!)，

  • tiles 长度为 n，最坏情况下 tiles 中所有字符不同，则问题等价于全排列，复杂度接近 O(n!)。
  • 但由于存在重复字符，实际复杂度远小于 O(n!)，大约 O(k^n)，其中 k 为不同字符的个数，最大为 26。

• 空间复杂度：O(n)

  • count 数组固定为 26，O(1)。
  • 递归深度最多 O(n)，因此总空间复杂度为 O(n)。

代码

/**
 * @param {string} tiles
 * @return {number}
 */
var numTilePossibilities = function (tiles) {
	let count = new Array(26).fill(0);
	for (let tile of tiles) {
		count[tile.charCodeAt() - 65]++;
	}
	const backtrack = (count) => {
		let total = 0;
		for (let i = 0; i < 26; i++) {
			if (count[i] == 0) {
				continue;
			}
			count[i]--;
			total += 1 + backtrack(count);
			count[i]++;
		}
		return total;
	};
	return backtrack(count);
};