Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go

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

• 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()
  
  

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

All Problems

All Solutions