回溯题目：字母组合迭代器

题目

标题和出处

标题：字母组合迭代器

出处：1286. 字母组合迭代器

难度

5 级

题目描述

要求

设计CombinationIterator \texttt{CombinationIterator}CombinationIterator类：

• CombinationIterator(string characters, int combinationLength) \texttt{CombinationIterator(string characters, int combinationLength)}CombinationIterator(string characters, int combinationLength)使用有序且字符唯一的小写字母组成的字符串characters \texttt{characters}characters和数字combinationLength \texttt{combinationLength}combinationLength初始化对象。
• next() \texttt{next()}next()返回字典序的下一个长度为combinationLength \texttt{combinationLength}combinationLength的下一个字母组合。
• hasNext() \texttt{hasNext()}hasNext()当且仅当存在下一个字母组合时返回true \texttt{true}true。

示例

示例 1：

输入：
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"] \texttt{["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]}["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []] \texttt{[["abc", 2], [], [], [], [], [], []]}[["abc", 2], [], [], [], [], [], []]
输出：
[null, "ab", true, "ac", true, "bc", false] \texttt{[null, "ab", true, "ac", true, "bc", false]}[null, "ab", true, "ac", true, "bc", false]
解释：
CombinationIterator iterator = new CombinationIterator("abc", 2); \texttt{CombinationIterator iterator = new CombinationIterator("abc", 2);}CombinationIterator iterator = new CombinationIterator("abc", 2);
iterator.next(); \texttt{iterator.next();}iterator.next();// 返回"ab" \texttt{"ab"}"ab"
iterator.hasNext(); \texttt{iterator.hasNext();}iterator.hasNext();// 返回true \texttt{true}true
iterator.next(); \texttt{iterator.next();}iterator.next();// 返回"ac" \texttt{"ac"}"ac"
iterator.hasNext(); \texttt{iterator.hasNext();}iterator.hasNext();// 返回true \texttt{true}true
iterator.next(); \texttt{iterator.next();}iterator.next();// 返回"bc" \texttt{"bc"}"bc"
iterator.hasNext(); \texttt{iterator.hasNext();}iterator.hasNext();// 返回false \texttt{false}false

数据范围

• 1 ≤ combinationLength ≤ characters.length ≤ 15 \texttt{1} \le \texttt{combinationLength} \le \texttt{characters.length} \le \texttt{15}1≤combinationLength≤characters.length≤15
• characters \texttt{characters}characters中每个字符按升序排序且各不相同
• 每组测试数据最多对next \texttt{next}next和hasNext \texttt{hasNext}hasNext调用10 4 \texttt{10}^\texttt{4}104次
• 保证每次调用函数next \texttt{next}next时都存在下一个字母组合

解法

思路和算法

这是一道设计题，要求设计字母组合迭代器。

为了实现迭代器，可以首先生成所有可能的组合列表并按升序排序，然后遍历列表，即可得到下一个字母组合与判断是否存在下一个字母组合。

生成所有可能的组合列表的做法为生成从n nn个字母中选k kk个字母的所有组合，其中n nn是字符串characters \textit{characters}characters的长度，k = combinationLength k = \textit{combinationLength}k=combinationLength。生成所有的k kk个字母的组合的做法是，从左到右遍历字符串characters \textit{characters}characters，每个字母都可以加入组合与不加入组合，对于同一个字母，依次考虑将其加入组合与不将其加入组合，当组合中的字母个数等于k kk时即得到一个目标组合。

由于每个组合的长度固定为k kk，因此在回溯过程中如果遇到不可能得到k kk个字母的组合的情况则可提前返回。如果组合中已有的字母加上剩余的全部字母得到的组合长度仍小于k kk，则当前组合的情况下一定不可能得到k kk个字母的组合，此时可提前返回。

由于字符串characters \textit{characters}characters中的字母按升序排序，因此字典序最小的组合是最前面k kk个字母组成的组合，字典序最大的组合是最后面k kk个字母组成的组合。考虑组合的第index \textit{index}index个字母，如果此时遍历到字符串characters \textit{characters}characters的下标i ii处（i < n − 1 i < n - 1i<n−1），则当characters [ i ] \textit{characters}[i]characters[i]加入组合时组合的第index \textit{index}index个字母是characters [ i ] \textit{characters}[i]characters[i]，当characters [ i ] \textit{characters}[i]characters[i]不加入组合时存在下标j > i j > ij>i使得组合的第index \textit{index}index个字母是characters [ j ] \textit{characters}[j]characters[j]，由于字符串characters \textit{characters}characters中的字母按升序排序，因此characters [ j ] > characters [ i ] \textit{characters}[j] > \textit{characters}[i]characters[j]>characters[i]，即characters [ i ] \textit{characters}[i]characters[i]加入组合对应的字母组合小于characters [ i ] \textit{characters}[i]characters[i]不加入组合对应的字母组合。因此，对于同一个字母，依次考虑将其加入组合与不将其加入组合，得到的所有k kk个字母的组合列表的顺序为字典序升序。

得到所有的k kk个字母的组合列表之后，维护当前组合的下标currCombinationIndex \textit{currCombinationIndex}currCombinationIndex，初始时currCombinationIndex = 0 \textit{currCombinationIndex} = 0currCombinationIndex=0。得到下一个字母组合与判断是否存在下一个字母组合的做法如下。

• 得到下一个字母组合：组合列表的下标currCombinationIndex \textit{currCombinationIndex}currCombinationIndex处的组合nextCombination \textit{nextCombination}nextCombination即为下一个字母组合，得到nextCombination \textit{nextCombination}nextCombination之后，将currCombinationIndex \textit{currCombinationIndex}currCombinationIndex加1 11，然后返回nextCombination \textit{nextCombination}nextCombination。

• 判断是否存在下一个字母组合：如果currCombinationIndex \textit{currCombinationIndex}currCombinationIndex小于组合列表的长度，则存在下一个字母组合，返回true \text{true}true，否则返回false \text{false}false。

代码

classCombinationIterator{List<String>combinations;Stringcharacters;StringBuffertemp;intcharactersLength,combinationLength;intcombinationsCount;intcurrCombinationIndex;publicCombinationIterator(Stringcharacters,intcombinationLength){this.combinations=newArrayList<String>();this.characters=characters;this.temp=newStringBuffer();this.charactersLength=characters.length();this.combinationLength=combinationLength;backtrack(0);this.combinationsCount=combinations.size();this.currCombinationIndex=0;}publicStringnext(){StringnextCombination=combinations.get(currCombinationIndex);currCombinationIndex++;returnnextCombination;}publicbooleanhasNext(){returncurrCombinationIndex<combinationsCount;}privatevoidbacktrack(intindex){if(temp.length()==combinationLength){combinations.add(temp.toString());}else{if(temp.length()+charactersLength-index<combinationLength){return;}temp.append(characters.charAt(index));backtrack(index+1);temp.deleteCharAt(temp.length()-1);backtrack(index+1);}}}

复杂度分析

• 时间复杂度：构造方法的时间复杂度是O ( k × C n k ) O(k \times C_n^k)O(k×Cnk​)，方法next \textit{next}next和hasNext \textit{hasNext}hasNext的时间复杂度是O ( 1 ) O(1)O(1)，其中n nn是字符串characters \textit{characters}characters的长度，k = combinationLength k = \textit{combinationLength}k=combinationLength。
  构造方法生成从n nn个字母中选k kk个字母的所有组合，可能的组合数共有C n k C_n^kCnk​个，对于每个组合需要O ( k ) O(k)O(k)的时间添加到列表中，因此时间复杂度是O ( k × C n k ) O(k \times C_n^k)O(k×Cnk​)。
  方法next \textit{next}next和hasNext \textit{hasNext}hasNext根据组合列表得到答案，时间复杂度是O ( 1 ) O(1)O(1)。

• 空间复杂度：O ( k × C n k ) ) O(k \times C_n^k))O(k×Cnk​))，其中n nn是字符串characters \textit{characters}characters的长度，k = combinationLength k = \textit{combinationLength}k=combinationLength。存储当前组合需要O ( k ) O(k)O(k)的空间，递归调用栈需要O ( n ) O(n)O(n)的空间，存储所有的k kk个字母的组合需要O ( k × C n k ) O(k \times C_n^k)O(k×Cnk​)的空间，因此空间复杂度是O ( k × C n k ) O(k \times C_n^k)O(k×Cnk​)。