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

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题字母组合迭代器出处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}abiterator.hasNext(); \texttt{iterator.hasNext();}iterator.hasNext();// 返回true \texttt{true}trueiterator.next(); \texttt{iterator.next();}iterator.next();// 返回ac \texttt{ac}aciterator.hasNext(); \texttt{iterator.hasNext();}iterator.hasNext();// 返回true \texttt{true}trueiterator.next(); \texttt{iterator.next();}iterator.next();// 返回bc \texttt{bc}bciterator.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≤15characters \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}kcombinationLength。生成所有的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 - 1in−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 iji使得组合的第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} 0currCombinationIndex0。得到下一个字母组合与判断是否存在下一个字母组合的做法如下。得到下一个字母组合组合列表的下标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{ListStringcombinations;Stringcharacters;StringBuffertemp;intcharactersLength,combinationLength;intcombinationsCount;intcurrCombinationIndex;publicCombinationIterator(Stringcharacters,intcombinationLength){this.combinationsnewArrayListString();this.characterscharacters;this.tempnewStringBuffer();this.charactersLengthcharacters.length();this.combinationLengthcombinationLength;backtrack(0);this.combinationsCountcombinations.size();this.currCombinationIndex0;}publicStringnext(){StringnextCombinationcombinations.get(currCombinationIndex);currCombinationIndex;returnnextCombination;}publicbooleanhasNext(){returncurrCombinationIndexcombinationsCount;}privatevoidbacktrack(intindex){if(temp.length()combinationLength){combinations.add(temp.toString());}else{if(temp.length()charactersLength-indexcombinationLength){return;}temp.append(characters.charAt(index));backtrack(index1);temp.deleteCharAt(temp.length()-1);backtrack(index1);}}}复杂度分析时间复杂度构造方法的时间复杂度是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}kcombinationLength。构造方法生成从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}kcombinationLength。存储当前组合需要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​)。