MediumNo. 1286
Iterator for Combination — LeetCode 1286 Python Solution
- Pattern
- Backtracking
- Topics
- Design, String, Backtracking, Iterator
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- ["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
- Output
- [null, "ab", true, "ac", true, "bc", false]
- Explanation
- CombinationIterator itr = new CombinationIterator("abc", 2);
Python solution
class CombinationIterator:
def __init__(self, characters: str, combinationLength: int):
def dfs(i):
if len(t) == combinationLength:
cs.append(''.join(t))
return
if i == n:
return
t.append(characters[i])
dfs(i + 1)
t.pop()
dfs(i + 1)
cs = []
n = len(characters)
t = []
dfs(0)
self.cs = cs
self.idx = 0
def next(self) -> str:
ans = self.cs[self.idx]
self.idx += 1
return ans
def hasNext(self) -> bool:
return self.idx < len(self.cs)
# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()Complexity
- Time
- Exponential (worst case)
- Space · auxiliary
- O(depth)
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1286. Iterator for Combination is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0079 | Word Search | Medium |
| 0093 | Restore IP Addresses | Medium |
| 0212 | Word Search II | Hard |
| 0257 | Binary Tree Paths | Easy |
| 0282 | Expression Add Operators | Hard |
| 0301 | Remove Invalid Parentheses | Hard |
Frequently asked questions
- How hard is LeetCode 1286. Iterator for Combination?
LeetCode 1286. Iterator for Combination is rated Medium on LeetCode.
- What topics does LeetCode 1286. Iterator for Combination cover?
LeetCode 1286. Iterator for Combination is tagged Design, String, Backtracking and Iterator on LeetCode.