Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

604. Design Compressed String Iterator

Time: Constructor: $O(|texttt{compressedString}|)$, next(), hasNext(): $O(1)$

Space: $O(|texttt{compressedString}|)$

			


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'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'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'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 + (ord(self.s[self.i]) - ord('0'))
        self.i += 1

    self.num -= 1
    return self.currentChar

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