1286. 字母组合迭代器 - Iterator for Combination

🎯 问题描述（来源于LeetCode）

描述：
设计一个迭代器类 CombinationIterator，它接收一个字符串 characters（由不同的小写字母组成）和一个整数 combinationLength。
要求按字典序生成所有长度为 combinationLength 的组合（每个组合是 characters 中按原顺序的子序列），并提供 next() 和 hasNext() 方法。

说明：

组合中的字母顺序必须与 characters 中的顺序一致（即只能取子序列，不能重排）。
生成的组合按字典序排列（即相当于先按第一个字符排序，再按第二个，等等）。

示例：

输入:
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
输出:
[null, "ab", true, "ac", true, "bc", false]

💻 解题思路

思路：DFS 预先生成所有组合 + 队列存储

算法步骤

在构造函数中：
- 初始化空列表 path 用于暂存当前组合，空队列 queue 用于存储所有组合。
- 定义递归函数 dfs(i)，表示处理到下标 i 的字符：
  - 如果 i == len(characters)：
    - 若 len(path) == combinationLength，则将当前组合（字符串）加入队列。
    - 返回。
  - 否则，分别尝试：
    - 选当前字符：将 characters[i] 加入 path，递归 dfs(i+1)，然后回溯弹出。
    - 不选当前字符：直接递归 dfs(i+1)。
- 调用 dfs(0) 生成所有组合。
next() 方法：从队列头部弹出一个组合并返回。
hasNext() 方法：返回队列是否非空。

代码实现

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        path = []
        self.queue = []
        def dfs(i):
            if i == len(characters):
                if len(path) == combinationLength:
                    self.queue.append(''.join(path))
                return 
            # 选当前字符
            path.append(characters[i])
            dfs(i+1)
            path.pop()
            # 不选当前字符
            dfs(i+1)
        dfs(0)        

    def next(self) -> str:
        return self.queue.pop(0)

    def hasNext(self) -> bool:
        return len(self.queue) != 0

📊 性能分析

构造函数时间复杂度： $O(2^n)$ ，其中 $n = len(characters)$ 。每个字符有选或不选两种可能，需要枚举所有子集。
空间复杂度： $O(C(n, k) \cdot k)$ ，用于存储所有组合，其中 $C(n, k)$ 是组合数。
next() 和 hasNext()： $O(1)$ 均摊（但 pop(0) 在 Python 中是 $O(m)$ ，m 为队列长度，可能影响性能，但题目数据范围较小，通常可接受）。

思考

该解法直接枚举所有组合并预先存储，调用 next() 时只需弹出即可，实现简单直观。
优点：

逻辑清晰，利用了经典的子集生成回溯模板。
易于理解和调试。

注意事项：

pop(0) 在列表头部弹出元素是 $O(n)$ 操作，若组合数量很大，可能效率较低。可以改用 collections.deque 或使用索引指针优化。
由于 characters 中的字符是唯一且按升序给出的，DFS 默认生成的组合顺序就是字典序（因为先选后不选，且递归顺序从左到右），所以无需额外排序。
另一种解法是使用“下一个组合”算法（类似于 next_permutation），可以节省预先生成的空间和时间，但实现稍复杂。对于本题输入限制（n ≤ 15），此预生成方法完全可行。