LeetCode-1286. Iterator for Combination

LeetCode-1286. Iterator for Combination

Design an Iterator class, which has:

A constructor that takes a string​​characters​​ ofsorted distinctlowercase English letters and a number​​combinationLength​​ as arguments.A functionnext()that returns the next combination of length​​combinationLength​​ inlexicographical order.A functionhasNext()that returns​​True​​ if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.iterator.next(); // returns "ab"iterator.hasNext(); // returns trueiterator.next(); // returns "ac"iterator.hasNext(); // returns trueiterator.next(); // returns "bc"iterator.hasNext(); // returns false

Constraints:

​​1 <= combinationLength <= characters.length <= 15​​There will be at most​​10^4​​ function calls per test.It's guaranteed that all calls of the function​​next​​ are valid.

题解：

class CombinationIterator {private: vector dic; int idx = 0; void buildIterator(int begin, string &cur, int combinationLength, string &characters) { if (cur.length() == combinationLength) { dic.push_back(cur); return; } for (int i = begin + 1; i < characters.length(); i++) { cur += characters[i]; buildIterator(i, cur, combinationLength, characters); cur.pop_back(); } }public: CombinationIterator(string characters, int combinationLength) { for (int i = 0; i < characters.size(); i++) { string cur; cur += characters[i]; buildIterator(i, cur, combinationLength, characters); } } string next() { return dic[idx++]; } bool hasNext() { return idx < dic.size(); }};/** * 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(); */

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。