Design Compressed String Iterator - Leetcode Solution

Design Compressed String Iterator is a problem on LeetCode that requires implementing a class that takes a compressed string input consisting of a letter and a count, and returns the letter at the current index of the iteration. The class should also have a method to check if there are more elements in the compressed string to iterate over.

The detailed solution for this problem is as follows:

1. Define a class CompressedStringIterator that takes the compressed string as input in its constructor. Initialize the current index of the iteration as 0.

2. Implement a method next() that returns the current letter and updates the current index based on the count of the letter. If the count is greater than 1, decrement the count and return the letter without updating the current index. If the count is 1, reset the count to 0 and increment the current index by 1.

3. Implement a method hasNext() that returns True if the current index is less than the length of the compressed string. Otherwise, return False.

4. In the constructor, initialize a variable last to store the last letter in the compressed string. Initialize a variable count to store the count of the last letter. Iterate over the compressed string from left to right, updating the values of last and count as necessary based on the current letter.

5. Finally, return the result of calling next() on the CompressedStringIterator object until hasNext() returns False.

The implementation of the CompressedStringIterator class will look something like this:

class CompressedStringIterator: def init(self, compressedString: str): self.compressedString = compressedString self.index = 0 self.last = self.compressedString[0] self.count = 0 for c in self.compressedString[1:]: if c.isdigit(): self.count = self.count * 10 + int(c) else: self.last = c

def next(self) -> str:
    if not self.hasNext():
        return ' '
    if self.count == 0:
        self.last = self.compressedString[self.index]
        self.index += 1
        while self.index < len(self.compressedString) and self.compressedString[self.index].isdigit():
            self.count = self.count * 10 + int(self.compressedString[self.index])
            self.index += 1
    if self.count > 1:
        self.count -= 1
        return self.last
    self.index += 1
    return self.last

def hasNext(self) -> bool:
    return self.index < len(self.compressedString)

The time complexity of the next() method is O(1) in the average case and O(n) in the worst case where n is the length of the compressed string. The space complexity of the class is O(1) because we are only storing the last letter, count, and current index.

1