604. Design Compressed String Iterator

Approach 1: Demand-Computation

• Time:
  • Constructor: $O(|\texttt{compressedString}|)$
  • next(): $O(1)$
  • hasNext(): $O(1)$
• Space: $O(|\texttt{compressedString}|)$

C++JavaPython

class StringIterator {
 public:
  StringIterator(string compressedString) : s(compressedString) {}

  char next() {
    if (!hasNext())
      return ' ';

    if (num == 0) {
      currentChar = s[i++];
      while (i < s.length() && isdigit(s[i]))
        num = num * 10 + (s[i++] - '0');
    }

    --num;
    return currentChar;
  }

  bool hasNext() {
    return i < s.length() || num > 0;
  }

 private:
  const string s;
  int i = 0;    // s' index
  int num = 0;  // currentChar's count
  char currentChar = ' ';
};

class StringIterator {
  public StringIterator(String compressedString) {
    s = compressedString;
  }

  public char next() {
    if (!hasNext())
      return ' ';

    if (num == 0) {
      currentChar = s.charAt(i++);
      while (i < s.length() && Character.isDigit(s.charAt(i)))
        num = num * 10 + (s.charAt(i++) - '0');
    }

    --num;
    return currentChar;
  }

  public boolean hasNext() {
    return i < s.length() || num > 0;
  }

  private final String s;
  private int i = 0;   // s' index
  private int num = 0; // currentChar's count
  private char currentChar = ' ';
}

class StringIterator:
  def __init__(self, compressedString: str):
    self.s = compressedString
    self.i = 0    # s' index
    self.num = 0  # currentChar's count
    self.currentChar = ' '

  def next(self) -> str:
    if not self.hasNext():
      return ' '

    if self.num == 0:
      self.currentChar = self.s[self.i]
      self.i += 1
      while self.i < len(self.s) and self.s[self.i].isdigit():
        self.num = self.num * 10 + int(self.s[self.i])
        self.i += 1

    self.num -= 1
    return self.currentChar

  def hasNext(self) -> bool:
    return self.i < len(self.s) or self.num > 0

Approach 2: Queue/Deque

• Time:
  • Constructor: $O(|\texttt{compressedString}|)$
  • next(): $O(1)$
  • hasNext(): $O(1)$
• Space: $O(|\texttt{compressedString}|)$

C++JavaPython

class StringIterator {
 public:
  StringIterator(string compressedString) {
    int i = 0;  // compressedString's index
    while (i < compressedString.length()) {
      const char c = compressedString[i++];
      int num = 0;
      while (i < compressedString.length() && isdigit(compressedString[i]))
        num = num * 10 + (compressedString[i++] - '0');
      q.emplace(c, num);
    }
  }

  char next() {
    if (!hasNext())
      return ' ';

    const char c = q.front().first;
    if (--q.front().second == 0)
      q.pop();
    return c;
  }

  bool hasNext() {
    return !q.empty();
  }

 private:
  queue<pair<char, int>> q;  // (currentChar, num)
};

class StringIterator {
  public StringIterator(String compressedString) {
    int i = 0; // compressedString's index
    while (i < compressedString.length()) {
      final char c = compressedString.charAt(i++);
      int num = 0;
      while (i < compressedString.length() && Character.isDigit(compressedString.charAt(i)))
        num = num * 10 + (compressedString.charAt(i++) - '0');
      q.offer(new Pair<>(c, num));
    }
  }

  public char next() {
    if (!hasNext())
      return ' ';

    final char c = q.peek().getKey();
    final int num = q.poll().getValue();
    if (num > 1)
      q.addFirst(new Pair<>(c, num - 1));
    return c;
  }

  public boolean hasNext() {
    return !q.isEmpty();
  }

  // (currentChar, num)
  private LinkedList<Pair<Character, Integer>> q = new LinkedList<>();
}

class StringIterator:
  def __init__(self, compressedString: str):
    self.q = collections.deque()  # (currentChar, num)

    i = 0  # compressedString's index
    while i < len(compressedString):
      c = compressedString[i]
      i += 1
      num = 0
      while i < len(compressedString) and compressedString[i].isdigit():
        num = num * 10 + int(compressedString[i])
        i += 1
      self.q.append((c, num))

  def next(self) -> str:
    if not self.hasNext():
      return ' '

    c, num = self.q.popleft()
    if num > 1:
      self.q.appendleft((c, num - 1))
    return c

  def hasNext(self) -> bool:
    return self.q