1286. Iterator for Combination

Description

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.

Solutions

• class CombinationIterator {
private int n;
private int combinationLength;
private String characters;
private StringBuilder t = new StringBuilder();
private List<String> cs = new ArrayList<>();
private int idx = 0;

public CombinationIterator(String characters, int combinationLength) {
n = characters.length();
this.combinationLength = combinationLength;
this.characters = characters;
dfs(0);
}

public String next() {
return cs.get(idx++);
}

public boolean hasNext() {
return idx < cs.size();
}

private void dfs(int i) {
if (t.length() == combinationLength) {
return;
}
if (i == n) {
return;
}
t.append(characters.charAt(i));
dfs(i + 1);
t.deleteCharAt(t.length() - 1);
dfs(i + 1);
}
}

/**
* Your CombinationIterator object will be instantiated and called as such:
* CombinationIterator obj = new CombinationIterator(characters, combinationLength);
* String param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/

• class CombinationIterator {
public:
string characters;
vector<string> cs;
int idx;
int n;
int combinationLength;
string t;

CombinationIterator(string characters, int combinationLength) {
idx = 0;
n = characters.size();
this->characters = characters;
this->combinationLength = combinationLength;
dfs(0);
}

string next() {
return cs[idx++];
}

bool hasNext() {
return idx < cs.size();
}

void dfs(int i) {
if (t.size() == combinationLength) {
cs.push_back(t);
return;
}
if (i == n) return;
t.push_back(characters[i]);
dfs(i + 1);
t.pop_back();
dfs(i + 1);
}
};

/**
* Your CombinationIterator object will be instantiated and called as such:
* CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
* string param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/

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

• type CombinationIterator struct {
cs  []string
idx int
}

func Constructor(characters string, combinationLength int) CombinationIterator {
t := []byte{}
n := len(characters)
cs := []string{}
var dfs func(int)
dfs = func(i int) {
if len(t) == combinationLength {
cs = append(cs, string(t))
return
}
if i == n {
return
}
t = append(t, characters[i])
dfs(i + 1)
t = t[:len(t)-1]
dfs(i + 1)
}
dfs(0)
return CombinationIterator{cs, 0}
}

func (this *CombinationIterator) Next() string {
ans := this.cs[this.idx]
this.idx++
return ans
}

func (this *CombinationIterator) HasNext() bool {
return this.idx < len(this.cs)
}

/**
* Your CombinationIterator object will be instantiated and called as such:
* obj := Constructor(characters, combinationLength);
* param_1 := obj.Next();
* param_2 := obj.HasNext();
*/