[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

Apply 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()

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments