LeetCode 1286. 字母组合迭代器（回溯/位运算）数据结构与算法Michael是个半路程序员-

1. 题目

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

• 一个构造函数，输入参数包括：一个 有序且字符唯一 的字符串 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 时都存在下一个字母组合。 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/iterator-for-combination
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 回溯

• 回溯法，先全部求出来，存起来备用

class CombinationIterator {  vector<string> ans;  string path; int id = 0; public: CombinationIterator(string characters, int combinationLength){ dfs(characters, combinationLength, 0); } void dfs(string &s, int n, int idx) { if(path.size() == n) {       ans.push_back(path); return; } for(int i = idx; i < s.size(); ++i) {       path.push_back(s[i]); dfs(s, n, i+1);//下一个字符只能更大+1开始找       path.pop_back(); } }     string next() { return ans[id++]; } bool hasNext() { return id < ans.size(); } }; 

32 ms 12.8 MB

2.2 位运算

class CombinationIterator { int bits;  string s; int len; public: CombinationIterator(string characters, int combinationLength) {      s = characters;      bits = (1<<s.size())-1;      len = combinationLength; } int countOne(int n) { int count = 0; while(n) {       count++;       n = n & (n-1); } return count; }     string next() { while(bits > 0 && countOne(bits) != len)       bits--;      string t; for(int i = s.size()-1; i >= 0; --i) { if((bits>>i)&1)        t += s[s.size()-i-1];//字符串是从左往右的，序号0开始 }         bits--;//下一个数，下次搜索的起点 return t; } bool hasNext() { while(bits > 0 && countOne(bits) != len)       bits--; return bits > 0; } }; 

20 ms 12 MB