Medium

题目描述

设计一个 CombinationIterator 类：

  • CombinationIterator(string characters, int combinationLength) 使用字符串 characters（由不同的小写英文字母组成且已排序）和数字 combinationLength 初始化对象。
  • next() 返回长度为 combinationLength 的下一个按字典序排列的组合。
  • hasNext() 当且仅当存在下一个组合时返回 true。

示例 1：

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

解释
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // 返回 "ab"
itr.hasNext(); // 返回 true
itr.next();    // 返回 "ac"
itr.hasNext(); // 返回 true
itr.next();    // 返回 "bc"
itr.hasNext(); // 返回 false

约束条件：

  • 1 <= combinationLength <= characters.length <= 15
  • characters 的所有字符都是唯一的
  • 最多调用 next 和 hasNext 函数 10^4 次
  • 保证所有 next 函数的调用都是有效的

提示：

  • 预处理生成所有组合
  • 使用位掩码生成所有组合

解题思路

这道题有两种主要的解决方案：

方法一：预生成所有组合 在初始化时，使用回溯算法生成所有长度为 combinationLength 的组合，并按字典序存储在列表中。然后维护一个索引指针，next() 返回当前组合并移动指针，hasNext() 检查是否还有剩余组合。这种方法时间复杂度集中在初始化阶段，查询操作都是 O(1)。

方法二：位掩码生成组合 利用位运算的特性，用一个整数的二进制表示来表示组合的选择状态。从最大的符合条件的掩码开始，每次调用 next() 时计算下一个有效的掩码。这种方法空间复杂度更优，但每次 next() 需要一定的计算时间。

推荐解法：预生成组合 考虑到题目限制字符串长度最多15，组合数量不会过大，且查询次数可能很多，预生成方法在实际使用中性能更好，代码也更简洁易懂。我们使用回溯算法生成所有组合，确保按字典序排列。

代码实现

class CombinationIterator {
private:
    vector<string> combinations;
    int index;
    
    void generateCombinations(const string& chars, int length, int start, string& current) {
        if (current.length() == length) {
            combinations.push_back(current);
            return;
        }
        
        for (int i = start; i < chars.length(); i++) {
            current.push_back(chars[i]);
            generateCombinations(chars, length, i + 1, current);
            current.pop_back();
        }
    }
    
public:
    CombinationIterator(string characters, int combinationLength) {
        index = 0;
        string current = "";
        generateCombinations(characters, combinationLength, 0, current);
    }
    
    string next() {
        return combinations[index++];
    }
    
    bool hasNext() {
        return index < combinations.size();
    }
};

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combinations = []
        self.index = 0
        self._generate_combinations(characters, combinationLength, 0, "")
    
    def _generate_combinations(self, chars, length, start, current):
        if len(current) == length:
            self.combinations.append(current)
            return
        
        for i in range(start, len(chars)):
            self._generate_combinations(chars, length, i + 1, current + chars[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)

public class CombinationIterator {
    private List<string> combinations;
    private int index;

    public CombinationIterator(string characters, int combinationLength) {
        combinations = new List<string>();
        index = 0;
        GenerateCombinations(characters, combinationLength, 0, "");
    }
    
    private void GenerateCombinations(string chars, int length, int start, string current) {
        if (current.Length == length) {
            combinations.Add(current);
            return;
        }
        
        for (int i = start; i < chars.Length; i++) {
            GenerateCombinations(chars, length, i + 1, current + chars[i]);
        }
    }
    
    public string Next() {
        return combinations[index++];
    }
    
    public bool HasNext() {
        return index < combinations.Count;
    }
}

var CombinationIterator = function(characters, combinationLength) {
    this.chars = characters;
    this.len = combinationLength;
    this.indices = [];
    for (let i = 0; i < combinationLength; i++) {
        this.indices[i] = i;
    }
    this.finished = false;
};

CombinationIterator.prototype.next = function() {
    if (!this.hasNext()) return "";
    
    let result = "";
    for (let i = 0; i < this.len; i++) {
        result += this.chars[this.indices[i]];
    }
    
    this.advance();
    return result;
};

CombinationIterator.prototype.hasNext = function() {
    return !this.finished;
};

CombinationIterator.prototype.advance = function() {
    let i = this.len - 1;
    while (i >= 0 && this.indices[i] == this.chars.length - this.len + i) {
        i--;
    }
    
    if (i < 0) {
        this.finished = true;
        return;
    }
    
    this.indices[i]++;
    for (let j = i + 1; j < this.len; j++) {
        this.indices[j] = this.indices[j - 1] + 1;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(C(n,k) * k)O(C(n,k) * k)
next()O(1)O(1)
hasNext()O(1)O(1)

其中 n 是字符串长度，k 是组合长度，C(n,k) 表示组合数。