604. Design Compressed String Iterator

Approach 1: Demand-Computation

• Time: Constructor: $O(|texttt{compressedString}|)$, next(), hasNext(): $O(1)$
• Space: $O(|texttt{compressedString}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 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 = ' '; }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 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 = ' '; } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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 

Approach 2: Queue/Deque

• Time: Constructor: $O(|texttt{compressedString}|)$, next(), hasNext(): $O(1)$
• Space: $O(|texttt{compressedString}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 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> q; // (currentChar, num) }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 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> q = new LinkedList<>(); } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 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 + (ord(compressedString[i]) - ord('0')) 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