iterator-for-combination_1286.py

# Design the CombinationIterator class:

# CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
# next() Returns the next combination of length combinationLength in lexicographical order.
# hasNext() Returns true if and only if there exists a next combination.

# Example 1:

# Input
# ["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
# [["abc", 2], [], [], [], [], [], []]
# Output
# [null, "ab", true, "ac", true, "bc", false]

# Explanation
# CombinationIterator itr = new CombinationIterator("abc", 2);
# itr.next();    // return "ab"
# itr.hasNext(); // return True
# itr.next();    // return "ac"
# itr.hasNext(); // return True
# itr.next();    // return "bc"
# itr.hasNext(); // return False


# Constraints:

# 1 <= combinationLength <= characters.length <= 15
# All the characters of characters are unique.
# At most 104 calls will be made to next and hasNext.
# It is guaranteed that all calls of the function next are valid.


# ---------------------------------------Runtime 99.23 ms Beats 35% Memory 18.58 MB Beats 91.89%---------------------------------------

from typing import Any, List


class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.combinationLength = combinationLength
        self.back = self.backtracking(list(characters), [])
        self.curr_char = next(self.back)
        self._next_val = True

    def backtracking(self, arr: List[Any], path: List[Any]):
        if len(path) == self.combinationLength:
            yield "".join(path)
        else:
            for i in range(len(arr)):
                path.append(arr[i])
                yield from self.backtracking(arr[i + 1 :], path)
                path.pop()

    def next(self) -> str:
        self.prev = self.curr_char
        try:
            self.curr_char = next(self.back)
            return self.prev
        except StopIteration:
            self._next_val = False
        return self.prev

    def hasNext(self) -> bool:
        return self._next_val


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