题目描述

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

一个构造函数，输入参数包括：一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength 。
函数 next() ，按 字典序 返回长度为 combinationLength 的下一个字母组合。
函数 hasNext() ，只有存在长度为 combinationLength 的下一个字母组合时，才返回 True；否则，返回 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
每组测试数据最多包含 10^4 次函数调用。
题目保证每次调用函数 next 时都存在下一个字母组合。

算法1

我的理解 大概就是DFS先生成各种组合吧 使用vector存储
然后再来应对 next hasnext的询问很简单的

C++ 代码

class CombinationIterator {
public:
    int idx = 0;
    vector<string> vstr;
    vector<char> ele;
    void dfs(const string& s, int len, int idx)
    {
        if (ele.size() == len) {
            string str(ele.begin(), ele.end());
            vstr.push_back(str);
            return;
        }
        else if (idx == s.size()) {
            return;
        }

        ele.push_back(s[idx]);
        dfs(s, len, idx + 1);
        ele.pop_back();

        dfs(s, len, idx + 1);
    }

    CombinationIterator(string characters, int combinationLength) {
        dfs(characters,combinationLength,0); 
        idx = 0;
    }

    string next() {
        return vstr[idx++];
    }

    bool hasNext() {
        if(idx < vstr.size())
            return true;

        return false;
    }
};

/**
 * 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();
 */