LeetCode 题解工作台
字母组合迭代器
请你设计一个迭代器类 CombinationIterator ，包括以下内容： CombinationIterator(string characters, int combinationLength) 一个构造函数，输入参数包括：用一个 有序且字符唯一 的字符串 characters （该字符串只…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们通过 枚举，预处理生成所有长度为 的字符串，存放到 数组中。 class CombinationIterator:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
请你设计一个迭代器类 CombinationIterator ，包括以下内容：
CombinationIterator(string characters, int combinationLength)一个构造函数，输入参数包括：用一个 有序且字符唯一 的字符串characters（该字符串只包含小写英文字母）和一个数字combinationLength。- 函数
next()，按 字典序 返回长度为combinationLength的下一个字母组合。 - 函数
hasNext()，只有存在长度为combinationLength的下一个字母组合时，才返回true
示例 1：
输入:
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
输出：
[null, "ab", true, "ac", true, "bc", false]
解释：
CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator
iterator.next(); // 返回 "ab"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "ac"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "bc"
iterator.hasNext(); // 返回 false
提示：
1 <= combinationLength <= characters.length <= 15-
characters中每个字符都 不同 - 每组测试数据最多对
next和hasNext调用104次 - 题目保证每次调用函数
next时都存在下一个字母组合。
解题思路
方法一：DFS 回溯
我们通过 枚举，预处理生成所有长度为 的字符串，存放到 数组中。
class CombinationIterator:
def __init__(self, characters: str, combinationLength: int):
def dfs(i):
if len(t) == combinationLength:
cs.append(''.join(t))
return
if i == n:
return
t.append(characters[i])
dfs(i + 1)
t.pop()
dfs(i + 1)
cs = []
n = len(characters)
t = []
dfs(0)
self.cs = cs
self.idx = 0
def next(self) -> str:
ans = self.cs[self.idx]
self.idx += 1
return ans
def hasNext(self) -> bool:
return self.idx < len(self.cs)
# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(C(n, k)) to precompute all combinations, where n is characters.length and k is combinationLength. Each next() and hasNext() call is O(1). Space complexity is also O(C(n, k)) to store all combinations for efficient iteration. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask about handling large input strings and optimizing precomputation.
- question_mark
Expect clarification questions on lexicographical ordering and index management.
- question_mark
They may probe memory trade-offs between storing all combinations versus generating on the fly.
常见陷阱
外企场景- error
Failing to prune branches during backtracking, leading to unnecessary computation.
- error
Incorrect pointer management causing next() to skip or repeat combinations.
- error
Ignoring lexicographical order in the combination generation.
进阶变体
外企场景- arrow_right_alt
Generate combinations lazily without precomputing to reduce memory usage.
- arrow_right_alt
Allow duplicate characters in the input string, requiring additional checks.
- arrow_right_alt
Support variable-length combinations instead of a fixed length.