Design an Iterator class, which has:
- A constructor that takes a string
characters
of sorted distinct lowercase English letters and a numbercombinationLength
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.
Solution: Bitmask
Use a bitmask to represent the chars selected.
start with (2^n – 1), decrease the mask until there are c bit set.
stop when mask reach to 0.
mask: 111 => abc
mask: 110 => ab
mask: 101 => ac
mask: 011 => bc
mask: 000 => “” Done
Time complexity: O(2^n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class CombinationIterator { public: CombinationIterator(string characters, int combinationLength): chars_(rbegin(characters), rend(characters)), length_(combinationLength), mask_((1 << characters.size()) - 1) {} string next() { hasNext(); string ans; for (int i = chars_.size() - 1; i >= 0 ; --i) if ((mask_ >> i) & 1) ans.push_back(chars_[i]); --mask_; return ans; } bool hasNext() { while (mask_ >= 0 && __builtin_popcount(mask_) != length_) --mask_; return mask_ > 0; } private: int mask_ = 0; const int length_; const string chars_; }; |