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.
class CombinationIterator:
def __init__(self, characters: str, combinationLength: int):
self.bitmasks = []
self.characters = characters
self.combinationLength = combinationLength
self.dfs(0, 0, [])
print(self.bitmasks)
def next(self) -> str:
ans = ""
mask = self.bitmasks.pop(0)
for i in range(len(mask)):
if mask[i] == "1":
ans += self.characters[i]
return ans
def hasNext(self) -> bool:
return self.bitmasks != []
def dfs(self, count, index, path):
if index == len(self.characters):
if count == self.combinationLength:
self.bitmasks.append(list(path))
return
for i in ["1", "0"]:
if count == self.combinationLength and i == "1":
continue
path.append(i)
if i == "1":
self.dfs(count+1, index+1, path)
else:
self.dfs(count, index+1, path)
path.pop()
class CombinationIterator:
def __init__(self, characters: str, combinationLength: int):
self.characters = characters
self.combinationLength = combinationLength
self.bitmasks = []
for mask in range(1 << len(characters)):
if bin(mask).count('1') == self.combinationLength:
res = ""
for i in range(len(characters)):
res = str(mask%2) + res
mask >>= 1
self.bitmasks.append(res)
self.bitmasks = self.bitmasks[::-1]
def next(self) -> str:
ans = ""
mask = self.bitmasks.pop(0)
for i in range(len(mask)):
if mask[i] == "1":
ans += self.characters[i]
return ans
def hasNext(self) -> bool:
return self.bitmasks != []