1286. Iterator for Combination

1286. Iterator for Combination (Medium)

Design an Iterator class, which has:

• A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
• A function next() that returns the next combination of length combinationLength in lexicographical order.
• A function hasNext() 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 true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.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.

Related Topics:
Backtracking, Design

Solution 1.

// OJ: https://leetcode.com/problems/iterator-for-combination/
// Author: github.com/lzl124631x
// Time:
//      CombinationIterator: O(S)
//      next: O(L)
//      hasNext: O(1)
// Space: O(S)
class CombinationIterator {
    vector<int> index;
    string s;
public:
    CombinationIterator(string s, int len) : s(s), index(len) {
        iota(begin(index), end(index), 0);
    }
    string next() {
        string ans; 
        for (int n : index) ans += s[n];
        for (int i = index.size() - 1; i >= 0; --i) {
            if (i > 0 && index[i] == s.size() - index.size() + i) continue;
            ++index[i++];
            for (; i < index.size(); ++i) index[i] = index[i - 1] + 1;
            break;
        }
        return ans;
    }
    bool hasNext() {
        return index[0] <= s.size() - index.size();
    }
};