Question

1286. Iterator for Combination

中文文档

Description

Design the CombinationIterator class:

• CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
• next() Returns the next combination of length combinationLength in lexicographical order.
• hasNext() Returns true if and only if there exists a next combination.

 

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();  // return "ab"
itr.hasNext(); // return True
itr.next();  // return "ac"
itr.hasNext(); // return True
itr.next();  // return "bc"
itr.hasNext(); // return False

 

Constraints:

• 1 <= combinationLength <= characters.length <= 15
• All the characters of characters are unique.
• At most 104 calls will be made to next and hasNext.
• It is guaranteed that all calls of the function next are valid.

Solutions

Solution 1

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();
 */

Solution 2

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();
 */