题目描述

请你设计一个迭代器类，包括以下内容：

• 一个构造函数，输入参数包括：一个有序且字符唯一的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength。
• 函数 next()，按字典序返回长度为 combinationLength 的下一个字母组合。
• 函数 hasNext()，当且仅当存在长度为 combinationLength 的下一个字母组合时，返回 True。

样例

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
• 每组测试数据最多包含 10^4 次函数调用。
• 题目保证每次调用函数 next 时都存在下一个字母组合。

算法

(按位处理) $O(L)$

1. 建一个长度为 combinationLength 的数组 v，每个位置存结果对应于原字符串的下标。如组合长度为 L，则初始时存储 [0, 1, 2, ..., L - 1]。
2. 调用 next 函数时直接依次取出字符，然后返回答案。接着从后向前找到最后一个位置，满足这个 v[i] + len - i < ch.length，然后这个位置的 v[pos]++，pos 之后的位置依次递增 1。
3. 如果找不到这样的位置，则标记不存在下一个。

时间复杂度

• 每次调用需要遍历整个长度的字符串，故时间复杂度为 $O(L)$。

空间复杂度

• 需要额外 $O(L)$ 的空间记录位置。

C++ 代码

class CombinationIterator {
public:
    vector<int> v;
    int len;
    string ch;
    bool nxt;

    CombinationIterator(string characters, int combinationLength) {
        ch = characters;
        len = combinationLength;
        v.resize(combinationLength);
        for (int i = 0; i < len; i++)
            v[i] = i;
        nxt = true;
    }

    string next() {
        string res;
        for (int i = 0; i < len; i++)
            res += ch[v[i]];

        int pos = -1;

        for (int i = len - 1; i >= 0; i--)
            if (v[i] + len - i < ch.length()) {
                pos = i;
                break;
            }

        if (pos != -1) {
            v[pos]++;
            for (int i = pos + 1; i < len; i++)
                v[i] = v[i - 1] + 1;
        } else {
            nxt = false;
        }

        return res;
    }

    bool hasNext() {
        return nxt;
    }
};

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */