本文共 1892 字，大约阅读时间需要 6 分钟。

1. 题目

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

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

示例：CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iteratoriterator.next(); // 返回 "ab"iterator.hasNext(); // 返回 trueiterator.next(); // 返回 "ac"iterator.hasNext(); // 返回 trueiterator.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
   
     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<
   
     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