字母组合迭代器

标签: 设计 字符串 回溯 迭代器

难度: Medium

请你设计一个迭代器类 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 时都存在下一个字母组合。

Submission

运行时间: 39 ms

内存: 18.8 MB

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combinations = []
        self.index = 0
        self.generate_combinations(characters, combinationLength, 0, '')

    def generate_combinations(self, characters, combinationLength, start, current):
        if len(current) == combinationLength:
            self.combinations.append(current)
            return
        
        for i in range(start, len(characters)):
            self.generate_combinations(characters, combinationLength, i + 1, current + characters[i])

    def next(self) -> str:
        result = self.combinations[self.index]
        self.index += 1
        return result

    def hasNext(self) -> bool:
        return self.index < len(self.combinations)

iterator = CombinationIterator("abc", 2)
print(iterator.next())  # 输出: "ab"
print(iterator.hasNext())  # 输出: True
print(iterator.next())  # 输出: "ac"
print(iterator.hasNext())  # 输出: True
print(iterator.next())  # 输出: "bc"
print(iterator.hasNext())  # 输出: False

Explain

这个题解采用了回溯算法来生成所有可能的组合，并将这些组合存储在一个列表中。在初始化阶段，会生成所有长度为 combinationLength 的字符组合。这些组合是按照字典顺序生成的，因为输入字符串是有序的。next() 方法简单地返回列表中的下一个组合，而 hasNext() 方法检查是否还有更多的组合可以返回。

时间复杂度: O(C(n, k) * k)

空间复杂度: O(C(n, k))

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combinations = []  # 存储生成的所有组合
        self.index = 0  # 当前返回组合的索引
        self.generate_combinations(characters, combinationLength, 0, '')

    def generate_combinations(self, characters, combinationLength, start, current):
        if len(current) == combinationLength:  # 基础情况：如果当前组合长度达到要求
            self.combinations.append(current)  # 添加到组合列表
            return
        
        for i in range(start, len(characters)):  # 从 start 开始生成所有可能的组合
            self.generate_combinations(characters, combinationLength, i + 1, current + characters[i])

    def next(self) -> str:  # 返回下一个组合
        result = self.combinations[self.index]  # 获取当前索引的组合
        self.index += 1  # 索引递增
        return result

    def hasNext(self) -> bool:  # 检查是否还有更多组合
        return self.index < len(self.combinations)

Explore

在初始化阶段生成所有可能的组合可以简化next和hasNext方法的逻辑，使它们可以更快地执行。预计算组合列表意味着next方法仅需要返回下一个元素，而hasNext方法只需检查当前索引与列表长度的关系。这种设计特别适用于需要频繁调用next和hasNext操作，且组合总数不会造成过大内存负担的情况。

该递归实现确实考虑了输入字符串为空或combinationLength为0的边界情况。当输入字符串为空时，由于递归函数在for循环中依赖字符长度，循环将不会执行，因此不会生成任何组合。当combinationLength为0时，基础情况将立即满足（即current长度为0），此时将一个空字符串添加到组合列表中，表示一个有效的空组合。

递归调用确实有可能在输入字符串非常长时导致栈溢出，尤其是递归深度与combinationLength直接相关。在现实中，如果combinationLength非常大，递归深度也会相应增加，可能会达到栈溢出的风险。在实际应用中，可以考虑使用迭代方法或其他技术来减少递归深度，或者限制输入大小和组合长度。

在hasNext方法中，self.index是当前组合的索引，而len(self.combinations)是预先生成的组合列表的总长度。每次调用next方法时，self.index增加1。当self.index等于len(self.combinations)时，表示所有组合已经被返回，此时self.index < len(self.combinations)将返回false，从而正确地指示没有更多的组合可以返回。这是一种简单而有效的方式来跟踪是否还有剩余的组合需要返回。