Iterator for Combination

MediumStringBacktrackingDesignIterator

Solution

Solution1: Backtracking

Backtracking을 통해, 모든 combinations를 구하는 방법

  public characters: string;
  public combinationLength: number;
  private currentIndex: number;
  private readonly combinations: string[];
 
  constructor(characters: string, combinationLength: number) {
    this.characters = characters;
    this.combinationLength = combinationLength;
    this.combinations = [];
    this.currentIndex = -1;
    this.generate();
  }
 
  private generate(s = '', startIndex = 0) {
    if (s.length === this.combinationLength) {
      this.combinations.push(s);
      return;
    }
 
    for (let i = startIndex; i < this.characters.length; i++) {
      this.generate(s + this.characters[i], i + 1);
    }
  }
 
  next(): string {
    if (!this.hasNext()) {
      return '';
    }
    this.currentIndex += 1;
    return this.combinations[this.currentIndex];
  }
 
  hasNext(): boolean {
    return this.currentIndex + 1 < this.combinations.length;
  }
}

Complexity

  • Time
    • CombinationIterator: O(LCN)
    • next: O(1)
    • hasNext: O(1)
  • Space: O(LCN)

Solution2: Bit Manipulation

Bit Manipulation을 사용하여 각각의 combination을 구하는 방법

예를 들어, abc에서, ab는 110, ac는 101과 같이 현재 combination을 Bit를 사용하여 구할 수 있다.

updateMask는 Gosper's hack을 사용하여, 현재 mask보다 다음으로 작은 비트의 개수가 N인 정수를 구할 수 있습니다.

export class CombinationIterator {
  public characters: string;
  public length: number;
  public combinationLength: number;
  private mask: number;
 
  constructor(characters: string, combinationLength: number) {
    this.characters = characters;
    this.length = characters.length;
    this.combinationLength = combinationLength;
    this.mask = ((1 << combinationLength) - 1) << (this.length - combinationLength);
  }
 
  private updateMask() {
    const t = this.mask + 1;
    const u = t ^ this.mask;
    const v = t & this.mask;
    this.mask = v - (v & -v) / (u + 1);
  }
 
  next(): string {
    let combination = '';
    for (let i = this.length - 1; 0 <= i; i--) {
      if (this.mask & (1 << i)) {
        combination += this.characters[this.length - i - 1];
      }
    }
    this.updateMask();
    return combination;
  }
 
  hasNext(): boolean {
    return Boolean(this.mask);
  }
}

Complexity

  • Time
    • CombinationIterator: O(L)
    • next: O(L)
    • hasNext: O(1)
  • Space: O(L)
LeetCode
Iterator for Combination
https://leetcode.com/problems/iterator-for-combination