题目大意：
字母组合迭代器
请你设计一个迭代器类，包括以下内容：
- 一个构造函数，输入参数包括：一个 有序且字符唯一 的字符串 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 时都存在下一个字母组合。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1286
解题思路分析：
本题的关键在于next()方法，连续调用该方法，实际上是要按字典顺序输出所有长度为 combinationLength 的子序列（注意不是子字符串）。解题时，我们需要先将所有符合要求的子序列按照字典顺序都保存到一个Queue里，每调用一次next()方法，从Queue中poll出一个元素即可。判断hasNext()时，只需要看Queue是否为空即可。
因此，本题重点就在于如何按照字典顺序得到所有长度为combinationLength的子序列。其实这类问题是典型的的递归题，因为字符串内的字符已经是有序排列的，因此我们可以从字符串头开始循环到末尾，按顺序取出一个字符合并到子序列中，接下来，将当前index加一并递归到子问题，在子问题中，同样循环index到字符串末尾，按顺序取出一个字符，继续递归，直到子序列字符串长度为 combinationLength 时，将该字符串添加到Queue中即可。
这种递归方式是完全按照字典顺序进行，因此最终Queue中的字符串列表一定是按照字典顺序排序的。
实现代码：
int mCombinationLength;
Queue<String> list=new LinkedList<>();
public CombinationIterator(String characters, int combinationLength) {
mCombinationLength=combinationLength;
// 递归查找所有长度为combinationLength的子序列
helper(characters,0,"");
}
public String next() {
return list.poll();
}
public boolean hasNext() {
return list.size()>0;
}
void helper(String s, int index, String temp){
// 如果子序列长度等于mCombinationLength
if(temp.length()==mCombinationLength){
// 将子序列添加到Queue并退出当前递归
list.offer(temp);
return;
}
// 从index开始顺序取一个字符添加到子序列，并递归
for(int i=index;i<s.length();i++){
helper(s, i+1,temp+s.charAt(i));
}
} 本解法执行时间为6ms。
Runtime: 6 ms, faster than 94.33% of Java online submissions for Iterator for Combination.
Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Iterator for Combination.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1286-iterator-for-combination-解题思路分析/