每日一题之字母组合迭代器

题目1286：字母组合迭代器

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

• 一个构造函数，输入参数包括：一个 有序且字符唯一 的字符串 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 <= combinationLength <= characters.length <= 15
• 每组测试数据最多包含 10^4 次函数调用。
• 题目保证每次调用函数 next 时都存在下一个字母组合。

分析

这题有两种方法：

方法1：由于最近都是在做回溯类型的算法题，这题在回溯类型下，所以先使用回溯方法做了一遍，就是先顺序列出所有的字母组合值存到容器里，之后顺序的取出来。

方法2：使用二进制编码方式，拿"abcd"，2举例，字典序排序应该如下：

ab
ac
ad
bc
bd
cd

对应的二进制如下

1100
1010
1001
0110
0101
0011

可以看出二进制是从大到小排列的，所以可以找出二进制1的个数等于字符串个数的数字，按照二进制编码从大到小的顺序，将字典序排序的字符串依次列举出来。

代码

方法1:

class CombinationIterator {
   public:
    CombinationIterator(string characters, int combinationLength) {
        dfs(characters, combinationLength, 0, "");
    }

    void dfs(string str, int len, int index, string path) {
        if (path.size() == len) {
            paths.push_back(path);
            return;
        }

        for (int i = index; i < str.size(); i++) {
            dfs(str, len, i + 1, path + str[i]);
        }
    }

    string next() {
        string str = paths[0];
        paths.pop_front();
        return str;
    }

    bool hasNext() { return paths.size() > 0; }

   private:
    deque<string> paths;
};

方法2:

class CombinationIterator {
public:
    CombinationIterator(string characters, int combinationLength) {
        reverse(characters.begin(), characters.end());
        this->characters = characters;
        this->cur = (1 << characters.size()) - 1;
        this->combinationLength = combinationLength;
    }
    
    int Count(int n){
        int count = 0;
        while (n != 0){
            count++;
            n = (n-1) & n;
        }
        return count;
    }
    
    string next() {    
        while (cur >= 0 && Count(cur) != combinationLength) {
            cur--;
        }
        
        string res;
        for (int i = 0; i < characters.size(); ++i) {
            if (cur & (1 << i)) { 
                res = characters[i] + res;
            }
        }
        cur--;
        
        return res;
    }

    bool hasNext() {  
        while (cur >= 0 && Count(cur) != combinationLength) {
            cur--;
        }
        if (cur < 0) {
            return false;
        }
        return true;
    }
private:
    int cur;
    int combinationLength;
    string characters;
};