1286. Iterator for Combination

Medium

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 10^4 calls will be made to next and hasNext.

• It is guaranteed that all calls of the function next are valid.

解題

type CombinationIterator struct {
    arr []string
}


func Constructor(characters string, combinationLength int) CombinationIterator {
    combinations := make([]string, 0)

    var backtrack func([]byte, int)
    backtrack = func (s []byte, start int) {
        if len(s) == combinationLength {
            combinations = append(combinations, string(s))
        } else {
            for i:=start; i<len(characters); i++ {
                s = append(s, characters[i])
                backtrack(s, i+1)
                s = s[:len(s)-1]
            }
        }
    }

    backtrack([]byte{}, 0)
    
    return CombinationIterator{ arr: combinations }
}

func (this *CombinationIterator) Next() string {
    if len(this.arr) == 0 {
        return ""
    }

    res := this.arr[0]
    this.arr = this.arr[1:]

    return res
}


func (this *CombinationIterator) HasNext() bool {
    if len(this.arr) == 0 {
        return false
    }
    return true
}


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