1286. Iterator for Combination

[Tcdian]

1286. Iterator for Combination

请你设计一个迭代器类，包括以下内容：

• 一个构造函数，输入参数包括：一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数- 字 combinationLength 。
• 函数 next() ，按 字典序 返回长度为 combinationLength 的下一个字母组合。
• 函数 hasNext() ，只有存在长度为 combinationLength 的下一个字母组合时，才返回 True；否则，返回 False。

Example

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

Note

• 1 <= combinationLength <= characters.length <= 15
• 每组测试数据最多包含 10^4 次函数调用。
• 题目保证每次调用函数 next 时都存在下一个字母组合。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string} characters
 * @param {number} combinationLength
 */
var CombinationIterator = function(characters, combinationLength) {
    this.characters = characters;
    this.combinationLength = combinationLength;
    this.nextValue = Array.from(new Array(combinationLength), (_, index) => index);
    this.done = false;
};

/**
 * @return {string}
 */
CombinationIterator.prototype.next = function() {
    const result = this.nextValue.map((index) => this.characters[index]).join('');
    this.done = true;
    for (let i = this.nextValue.length - 1; i >= 0; i--) {
        if (this.nextValue[i] < this.characters.length - 1 - (this.nextValue.length - 1 - i)) {
            this.nextValue[i] += 1;
            for (let j = i + 1; j < this.nextValue.length; j++) {
                this.nextValue[j] = this.nextValue[j - 1] + 1;
            }
            this.done = false;
            break;
        }
    }
    return result;
};

/**
 * @return {boolean}
 */
CombinationIterator.prototype.hasNext = function() {
    return !this.done;
};

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

• TypeScript Solution

class CombinationIterator {
    nextValue: number[];
    done: boolean;
    constructor(private characters: string, private combinationLength: number) {
        this.nextValue = Array.from(new Array(combinationLength), (_, index) => index);
        this.done = false;
    }

    next(): string {
        const result = this.nextValue.map((index) => this.characters[index]).join('');
        this.done = true;
        for (let i = this.nextValue.length - 1; i >= 0; i--) {
            if (this.nextValue[i] < this.characters.length - 1 - (this.nextValue.length - 1 - i)) {
                this.nextValue[i] += 1;
                for (let j = i + 1; j < this.nextValue.length; j++) {
                    this.nextValue[j] = this.nextValue[j - 1] + 1;
                }
                this.done = false;
                break;
            }
        }
        return result;
    }

    hasNext(): boolean {
        return !this.done;
    }
}

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