Question

1286. 字母组合迭代器

English Version

题目描述

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

• CombinationIterator(string characters, int combinationLength) 一个构造函数，输入参数包括：用一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength 。
• 函数 _next() _，按 字典序 返回长度为 combinationLength 的下一个字母组合。
• 函数 _hasNext() _，只有存在长度为 combinationLength 的下一个字母组合时，才返回 true

 

示例 1：

输入:
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
输出：
[null, "ab", true, "ac", true, "bc", 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
•  characters 中每个字符都 不同
• 每组测试数据最多对 next 和 hasNext 调用 104次
• 题目保证每次调用函数 next 时都存在下一个字母组合。

解法

方法一：DFS 回溯

我们通过 $DFS$ 枚举，预处理生成所有长度为 $combinationLength$ 的字符串，存放到 $cs$ 数组中。

class CombinationIterator:
  def __init__(self, characters: str, combinationLength: int):
    def dfs(i):
      if len(t) == combinationLength:
        cs.append(''.join(t))
        return
      if i == n:
        return
      t.append(characters[i])
      dfs(i + 1)
      t.pop()
      dfs(i + 1)

    cs = []
    n = len(characters)
    t = []
    dfs(0)
    self.cs = cs
    self.idx = 0

  def next(self) -> str:
    ans = self.cs[self.idx]
    self.idx += 1
    return ans

  def hasNext(self) -> bool:
    return self.idx < len(self.cs)


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class CombinationIterator {
  private int n;
  private int combinationLength;
  private String characters;
  private StringBuilder t = new StringBuilder();
  private List<String> cs = new ArrayList<>();
  private int idx = 0;

  public CombinationIterator(String characters, int combinationLength) {
    n = characters.length();
    this.combinationLength = combinationLength;
    this.characters = characters;
    dfs(0);
  }

  public String next() {
    return cs.get(idx++);
  }

  public boolean hasNext() {
    return idx < cs.size();
  }

  private void dfs(int i) {
    if (t.length() == combinationLength) {
      cs.add(t.toString());
      return;
    }
    if (i == n) {
      return;
    }
    t.append(characters.charAt(i));
    dfs(i + 1);
    t.deleteCharAt(t.length() - 1);
    dfs(i + 1);
  }
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * String param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

class CombinationIterator {
public:
  string characters;
  vector<string> cs;
  int idx;
  int n;
  int combinationLength;
  string t;

  CombinationIterator(string characters, int combinationLength) {
    idx = 0;
    n = characters.size();
    this->characters = characters;
    this->combinationLength = combinationLength;
    dfs(0);
  }

  string next() {
    return cs[idx++];
  }

  bool hasNext() {
    return idx < cs.size();
  }

  void dfs(int i) {
    if (t.size() == combinationLength) {
      cs.push_back(t);
      return;
    }
    if (i == n) return;
    t.push_back(characters[i]);
    dfs(i + 1);
    t.pop_back();
    dfs(i + 1);
  }
};

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

type CombinationIterator struct {
  cs  []string
  idx int
}

func Constructor(characters string, combinationLength int) CombinationIterator {
  t := []byte{}
  n := len(characters)
  cs := []string{}
  var dfs func(int)
  dfs = func(i int) {
    if len(t) == combinationLength {
      cs = append(cs, string(t))
      return
    }
    if i == n {
      return
    }
    t = append(t, characters[i])
    dfs(i + 1)
    t = t[:len(t)-1]
    dfs(i + 1)
  }
  dfs(0)
  return CombinationIterator{cs, 0}
}

func (this *CombinationIterator) Next() string {
  ans := this.cs[this.idx]
  this.idx++
  return ans
}

func (this *CombinationIterator) HasNext() bool {
  return this.idx < len(this.cs)
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * obj := Constructor(characters, combinationLength);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */

方法二：二进制编码

我们看个例子，对于 $abcd$，若 $combinationLength$ 为 2，则 $cs$ 就是 $ab, ac, ad, bc, bd, cd, …$。

对应的二进制数为：

1100
1010
1001
0110
0101
0011
...

观察到上述规律后，我们依次按照二进制编码从大到小的规律，将所有字符串依次求出。

所谓的长度 $combinationLength$，只需要满足二进制编码中 $1$ 的个数满足要求即可。

class CombinationIterator:
  def __init__(self, characters: str, combinationLength: int):
    self.curr = (1 << len(characters)) - 1
    self.size = combinationLength
    self.cs = characters[::-1]

  def next(self) -> str:
    while self.curr >= 0 and self.curr.bit_count() != self.size:
      self.curr -= 1
    ans = []
    for i in range(len(self.cs)):
      if (self.curr >> i) & 1:
        ans.append(self.cs[i])
    self.curr -= 1
    return ''.join(ans[::-1])

  def hasNext(self) -> bool:
    while self.curr >= 0 and self.curr.bit_count() != self.size:
      self.curr -= 1
    return self.curr >= 0


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class CombinationIterator {
  private int curr;
  private int size;
  private char[] cs;

  public CombinationIterator(String characters, int combinationLength) {
    int n = characters.length();
    curr = (1 << n) - 1;
    size = combinationLength;
    cs = new char[n];
    for (int i = 0; i < n; ++i) {
      cs[i] = characters.charAt(n - i - 1);
    }
  }

  public String next() {
    while (curr >= 0 && Integer.bitCount(curr) != size) {
      --curr;
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < cs.length; ++i) {
      if (((curr >> i) & 1) == 1) {
        ans.append(cs[i]);
      }
    }
    --curr;
    return ans.reverse().toString();
  }

  public boolean hasNext() {
    while (curr >= 0 && Integer.bitCount(curr) != size) {
      --curr;
    }
    return curr >= 0;
  }
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * String param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

class CombinationIterator {
public:
  int size;
  string cs;
  int curr;

  CombinationIterator(string characters, int combinationLength) {
    int n = characters.size();
    curr = (1 << n) - 1;
    reverse(characters.begin(), characters.end());
    cs = characters;
    size = combinationLength;
  }

  string next() {
    while (curr >= 0 && __builtin_popcount(curr) != size) --curr;
    string ans;
    for (int i = 0; i < cs.size(); ++i) {
      if ((curr >> i) & 1) {
        ans += cs[i];
      }
    }
    reverse(ans.begin(), ans.end());
    --curr;
    return ans;
  }

  bool hasNext() {
    while (curr >= 0 && __builtin_popcount(curr) != size) --curr;
    return curr >= 0;
  }
};

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

type CombinationIterator struct {
  curr int
  size int
  cs   []byte
}

func Constructor(characters string, combinationLength int) CombinationIterator {
  n := len(characters)
  curr := (1 << n) - 1
  size := combinationLength
  cs := make([]byte, n)
  for i := range characters {
    cs[n-i-1] = characters[i]
  }
  return CombinationIterator{curr, size, cs}
}

func (this *CombinationIterator) Next() string {
  for this.curr >= 0 && bits.OnesCount(uint(this.curr)) != this.size {
    this.curr--
  }
  ans := []byte{}
  for i := range this.cs {
    if (this.curr >> i & 1) == 1 {
      ans = append(ans, this.cs[i])
    }
  }
  for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    ans[i], ans[j] = ans[j], ans[i]
  }
  this.curr--
  return string(ans)
}

func (this *CombinationIterator) HasNext() bool {
  for this.curr >= 0 && bits.OnesCount(uint(this.curr)) != this.size {
    this.curr--
  }
  return this.curr >= 0
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * obj := Constructor(characters, combinationLength);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */