题目

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

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

解题思路分析

1、模拟；时间复杂度O(n)，空间复杂度O(n)

type CombinationIterator struct {
   flag bool
   s    string
   arr  []int
}

func Constructor(characters string, combinationLength int) CombinationIterator {
   arr := make([]int, combinationLength)
   for i := 0; i < combinationLength; i++ {
      arr[i] = i
   }
   return CombinationIterator{
      flag: false,
      s:    characters,
      arr:  arr,
   }
}

func (this *CombinationIterator) Next() string {
   res := ""
   for i := 0; i < len(this.arr); i++ {
      res = res + string(this.s[this.arr[i]])
   }
   index := -1
   for i := len(this.arr) - 1; i >= 0; i-- {
      // 正常情况下：以abcdef 3 为例子
      // 0 1 5 => abf  下一个 acd
      // 6-3+2 = 5
      // 6-3+1 != 1 => index = 1
      // 然后: arr[index]+1，后面递增
      target := len(this.s) - len(this.arr) + i
      if this.arr[i] != target { // 从右到左边：找到
         index = i
         break
      }
   }
   if index == -1 { // 没有更大的
      this.flag = true
   } else {
      this.arr[index]++
      for i := index + 1; i < len(this.arr); i++ {
         this.arr[i] = this.arr[i-1] + 1
      }
   }
   return res
}

func (this *CombinationIterator) HasNext() bool {
   return this.flag == false
}

2、递归；时间复杂度O(n!)，空间复杂度O(n!)

type CombinationIterator struct {
   arr   []string
   index int
}

func dfs(str string, k int, index int, cur string, res *[]string) {
   if len(cur) == k {
      *res = append(*res, cur)
      return
   }
   for i := index; i < len(str); i++ {
      dfs(str, k, i+1, cur+string(str[i]), res)
   }
}
func Constructor(characters string, combinationLength int) CombinationIterator {
   res := make([]string, 0)
   dfs(characters, combinationLength, 0, "", &res)
   return CombinationIterator{
      arr:   res,
      index: 0,
   }
}

func (this *CombinationIterator) Next() string {
   if this.index < len(this.arr) {
      this.index++
      return this.arr[this.index-1]
   }
   return ""
}

func (this *CombinationIterator) HasNext() bool {
   return this.index < len(this.arr)
}

总结

Medium题目，可以每次调用的使用进行模拟，也可以全排列所有组合，然后返回结果