# [Leetcode]1286. Iterator for Combination

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.
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.
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

The key is to generate all combinations in lexicographical order, and return them accordingly. This post will first introduce two different approaches with DFS and bit masking. Then, an advanced solution using generators will be explained.

## Approach 1 – Bit masking

Taking ('abc',2) as an example, if we list binary representations of numbers 1 to 7, we can find that when number of set bits = combinationLength, applying bit masking to our input characters would generate the combinations in lexicographical order.

class CombinationIterator:
def __init__(self, characters: str, combinationLength: int):
self.ret = []
self.cur = 0
for i in range(1,1<<len(characters)):
seq = ''
num = i
j = len(characters)-1
while num:
if num & 1:
seq = characters[j] + seq
num >>= 1
j -= 1
if len(seq) == combinationLength:
self.ret.insert(0,seq)

def next(self) -> str:
ret = self.ret[self.cur]
self.cur += 1
return ret

def hasNext(self) -> bool:
if self.cur == len(self.ret):
return False
return True

## Approach 2 – DFS

Besides the above approach, it could also be solved with a typical depth-first-search algorithm (or backtracking). You can find more about DFS/backtracking here: [Leetcode for Interviews]DFS, BFS, and Backtracking II – How to backtrack? Detailed Explanations with Examples.

class CombinationIterator:

def __init__(self, characters: str, combinationLength: int):
self.ret = []
self.cur = 0

def helper(ind=0,cur=''):
if len(cur) == combinationLength:
self.ret.append(cur)
else:
for i in range(ind,len(characters)):
helper(i+1,cur+characters[i])
helper()

def next(self) -> str:
ret = self.ret[self.cur]
self.cur += 1
return ret

def hasNext(self) -> bool:
if self.cur == len(self.ret):
return False
return True

## Approach 2.5 – DFS + Generators

Simply speaking, generator functions return lazy iterators so that you can loop through. However, it does not store all contents in the memory, so it’s a memory-friendly operation. More details about generators: How to Use Generators and yield in Python.

class CombinationIterator:

def __init__(self, characters: str, combinationLength: int):
def helper(ind=0,cur=''):
if len(cur) == combinationLength:
yield cur
else:
for i in range(ind,len(characters)):
yield from helper(i+1,cur+characters[i])
self.combinations = helper()
self.next_checked = False
self.current = ''

def next(self) -> str:
if self.hasNext():
self.next_checked = False
return self.current

def hasNext(self) -> bool:
if self.next_checked:
return bool(self.current)
self.current = next(self.combinations,False)
self.next_checked = True
return bool(self.current)

# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

Subscribe
Notify of