請你設計一個迭代器類，包括以下內容：
一個構造函數，輸入參數包括：一個 有序且字符唯一 的字符串 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;
};
代碼精進之路
代碼精進之路，我們一起成長！