Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1286.html
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 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.
Related Topics:
Backtracking, Design
Solution 1.
-
class CombinationIterator { private int curr; private int size; private char[] cs; public CombinationIterator(String characters, int combinationLength) { int n = characters.length(); curr = (1 << n) - 1; size = combinationLength; cs = new char[n]; for (int i = 0; i < n; ++i) { cs[i] = characters.charAt(n - i - 1); } } public String next() { while (curr >= 0 && Integer.bitCount(curr) != size) { --curr; } StringBuilder ans = new StringBuilder(); for (int i = 0; i < cs.length; ++i) { if (((curr >> i) & 1) == 1) { ans.append(cs[i]); } } --curr; return ans.reverse().toString(); } public boolean hasNext() { while (curr >= 0 && Integer.bitCount(curr) != size) { --curr; } return curr >= 0; } } /** * Your CombinationIterator object will be instantiated and called as such: * CombinationIterator obj = new CombinationIterator(characters, combinationLength); * String param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */
-
class CombinationIterator { public: int size; string cs; int curr; CombinationIterator(string characters, int combinationLength) { int n = characters.size(); curr = (1 << n) - 1; reverse(characters.begin(), characters.end()); cs = characters; size = combinationLength; } string next() { while (curr >= 0 && __builtin_popcount(curr) != size) --curr; string ans; for (int i = 0; i < cs.size(); ++i) { if ((curr >> i) & 1) { ans += cs[i]; } } reverse(ans.begin(), ans.end()); --curr; return ans; } bool hasNext() { while (curr >= 0 && __builtin_popcount(curr) != size) --curr; return curr >= 0; } }; /** * 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(); */
-
class CombinationIterator: def __init__(self, characters: str, combinationLength: int): self.curr = (1 << len(characters)) - 1 self.size = combinationLength self.cs = characters[::-1] def next(self) -> str: while self.curr >= 0 and self.curr.bit_count() != self.size: self.curr -= 1 ans = [] for i in range(len(self.cs)): if (self.curr >> i) & 1: ans.append(self.cs[i]) self.curr -= 1 return ''.join(ans[::-1]) def hasNext(self) -> bool: while self.curr >= 0 and self.curr.bit_count() != self.size: self.curr -= 1 return self.curr >= 0 # Your CombinationIterator object will be instantiated and called as such: # obj = CombinationIterator(characters, combinationLength) # param_1 = obj.next() # param_2 = obj.hasNext()
-
type CombinationIterator struct { curr int size int cs []byte } func Constructor(characters string, combinationLength int) CombinationIterator { n := len(characters) curr := (1 << n) - 1 size := combinationLength cs := make([]byte, n) for i := range characters { cs[n-i-1] = characters[i] } return CombinationIterator{curr, size, cs} } func (this *CombinationIterator) Next() string { for this.curr >= 0 && bits.OnesCount(uint(this.curr)) != this.size { this.curr-- } ans := []byte{} for i := range this.cs { if (this.curr >> i & 1) == 1 { ans = append(ans, this.cs[i]) } } for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 { ans[i], ans[j] = ans[j], ans[i] } this.curr-- return string(ans) } func (this *CombinationIterator) HasNext() bool { for this.curr >= 0 && bits.OnesCount(uint(this.curr)) != this.size { this.curr-- } return this.curr >= 0 } /** * Your CombinationIterator object will be instantiated and called as such: * obj := Constructor(characters, combinationLength); * param_1 := obj.Next(); * param_2 := obj.HasNext(); */