题目描述

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

• 一个构造函数，输入参数包括：一个有序且字符唯一的字符串characters（该字符串只包含小写英文字母）和一个数字combinationLength。

• 函数next()，按字典序返回长度为combinationLength 的下一个字母组合。

• 函数hasNext()，只有存在长度为combinationLength 的下一个字母组合时，才返回True；否则，返回 False。

样例

CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator

iterator.next(); // 返回 "ab"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "ac"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "bc"
iterator.hasNext(); // 返回 false

算法1

按位操作 不确定叫啥名， 瞎起的

用数组ids来存储组合每位字符的下标. 字典序最小的组合下标为0 ~ m - 1, m 为combinationLength.
当进行next操作时在ids数组中从右向左找第一位可以+1的元素将其+1, 然后将其右边的元素顺次+1即可.

时间复杂度

初始化: $O(m)$, 其中$m$为combinationLength
next: $O(m)$
hasNext: $O(1)$

参考文献

java 代码

class CombinationIterator {
    int n;
    char[] chars;
    int total = 1;
    int idx = 0;
    int[] ids;

    public CombinationIterator(String characters, int combinationLength) {
        n = characters.length();
        chars = characters.toCharArray();
        for (int i = 0; i < combinationLength; i++) {
            total *= n - i;
        }
        for (int i = 1; i <= combinationLength; i++) {
            total /= i;
        }

        ids = new int[combinationLength];

        for (int i = 0; i < combinationLength; i++) {
            ids[i] = i;
        }
    }

    public String next() {
        StringBuilder sb = new StringBuilder();

        for (int id: ids) {
            sb.append(Character.toString(chars[id]));
        }

        idx++;
        if (idx < total) {
            for (int i = 0; i < ids.length; i++) {
                if (ids[ids.length - i - 1] < n - i - 1) {
                    ids[ids.length - i - 1] ++;
                    for (int k = ids.length - i; k < ids.length; k++) {
                        ids[k] = ids[k - 1] + 1;
                    }
                    break;
                }
            }
        }

        return sb.toString();
    }

    public boolean hasNext() {
        return idx < total;
    }
}

/**
 * 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();
 */