What is the main approach to solve Letter Tile Possibilities?

Use backtracking DFS combined with a hash map to track letter counts and prune invalid sequences efficiently.

How do I handle duplicate letters in tiles?

Count the frequency of each letter and decrement counts during recursion to avoid generating identical sequences multiple times.

What is the time complexity for this problem?

The time complexity is O(2^n * n), accounting for all subsets and permutations of tile sequences.

Can I generate all sequences instead of counting?

Yes, modify the DFS to append each sequence to a result list instead of just incrementing a counter.

Why is pruning important in backtracking for this problem?

Pruning prevents exploring invalid paths and avoids redundant computations, especially when tiles contain duplicates.

#1079

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

活字印刷

你有一套活字字模 tiles ，其中每个字模上都刻有一个字母 tiles[i] 。返回你可以印出的非空字母序列的数目。注意：本题中，每个活字字模只能使用一次。示例 1：输入： "AAB" 输出： 8 解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", …

哈希表字符串回溯计数

题目描述

你有一套活字字模 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 由大写英文字母组成

lightbulb

解题思路

方法一：计数 + 回溯

我们先用一个哈希表或数组 $cnt$ 统计每个字母出现的次数。

接下来定义一个函数 $dfs(cnt)$ ，表示当前剩余字母的计数为 $cnt$ 时，能够组成的不同序列的个数。

在 $dfs$ 中，我们枚举 $cnt$ 中每个大于 $0$ 的值 $cnt[i]$ ，将 $cnt[i]$ 减 $1$ 表示使用了这个字母，序列个数加 $1$ ，然后进行下一层搜索，在搜索结束后，累加返回的序列个数，然后将 $cnt[i]$ 加 $1$ 。最后返回序列个数。

时间复杂度 $O(n \times n!)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字母种类数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def dfs(cnt: Counter) -> int:
            ans = 0
            for i, x in cnt.items():
                if x > 0:
                    ans += 1
                    cnt[i] -= 1
                    ans += dfs(cnt)
                    cnt[i] += 1
            return ans

        cnt = Counter(tiles)
        return dfs(cnt)

speed

复杂度分析

指标	值
时间	complexity is O(2^n * n) because each subset of tiles may generate sequences up to length n, and space complexity is O(2^n * n) due to storing counts during recursion.
空间	O(2^n \cdot n)

psychology

面试官常问的追问

外企场景

question_mark
Pay attention to duplicate letters and avoid counting identical sequences multiple times.
question_mark
Consider using a hash map for tracking available letters instead of generating permutations blindly.
question_mark
Focus on pruning paths early to keep recursion efficient for the maximum of 7 tiles.

warning

常见陷阱

外企场景

error
Failing to account for duplicate letters, leading to overcounting sequences.
error
Not decrementing letter counts correctly in recursion, causing incorrect sequence totals.
error
Trying to generate all permutations explicitly instead of pruning with backtracking.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count sequences allowing repeated usage of the same tile multiple times.
arrow_right_alt
Find the lexicographically smallest sequence of a given length using the tiles.
arrow_right_alt
Return all unique sequences instead of just counting them.

help

常见问题

外企场景

继续练习

#1160 拼写单词 #1189 “气球” 的最大数量 #884 两句话中的不常见单词