LeetCode 1286. Iterator for Combination

Posted on | In |
Words count in article: 208 | Reading time ≈ 1

题目

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:

1
2
3
4
5
6
7
8
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.

思路

Python built-in itertools.combinations.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class CombinationIterator(object):

    def __init__(self, characters, combinationLength):
        """
        :type characters: str
        :type combinationLength: int
        """
        self.data = itertools.combinations(characters, combinationLength)
        self.last = characters[-combinationLength:]
        self.res = None

    def next(self):
        """
        :rtype: str
        """
        self.res = "".join(next(self.data))
        return self.res

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.last != self.res


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