Formatted question description: https://leetcode.ca/all/604.html

604. Design Compressed String Iterator (Easy)

Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext.

The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.

next() - if the original string still has uncompressed characters, return the next letter; Otherwise return a white space.
hasNext() - Judge whether there is any letter needs to be uncompressed.

Example:

StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");

iterator.next(); // return 'L'
iterator.next(); // return 'e'
iterator.next(); // return 'e'
iterator.next(); // return 't'
iterator.next(); // return 'C'
iterator.next(); // return 'o'
iterator.next(); // return 'd'
iterator.hasNext(); // return true
iterator.next(); // return 'e'
iterator.hasNext(); // return false
iterator.next(); // return ' '

Solution 1.

Let index points to the letter to output, nextIndex points to the next letter to output, cnt is the number of remaining occurrence of the current letter.

A function load is used to load the next letter, if neccessary. It will be called when there is a need to load the next letter, i.e., in constructor and in next.

// OJ: https://leetcode.com/problems/design-compressed-string-iterator
// Time: O(1)
// Space: O(1)
class StringIterator {
private:
  string str;
  int index = 0, nextIndex = 0, cnt = 0;
  void load() {
    while (index < str.size() && !cnt) {
      index = nextIndex;
      nextIndex = index + 1;
      while (nextIndex < str.size() && isdigit(str[nextIndex])) cnt = cnt * 10 + str[nextIndex++] - '0';
    }
  }
public:
  StringIterator(string compressedString) : str(compressedString) {
    load();
  }

  char next() {
    if (!hasNext()) return ' ';
    char ans = str[index];
    --cnt;
    load();
    return ans;
  }

  bool hasNext() {
    return index < str.size();
  }
};

Solution Java

In the constructor, split out each term that is a (character, count) pair. Then for each pair, split out the character and the count. Use two arrays to store the letters and the corresponding counts respectively. Both arrays have the same length. Initialize the index to 0.

For next operation, if there exists a next character, then obtain the character at the index as the return value, decrease the count at the index by 1. If the count at the index becomes 0 after decreasing, move to the next index. Return the character which is the return value. If there doesn’t exist a next character, return a space.

For hasNext operation, simply return whether the index is less than the length of both arrays.

class StringIterator {
    char[] letters;
    int[] counts;
    int length;
    int index;

    public StringIterator(String compressedString) {
        StringBuffer sb = new StringBuffer(compressedString);
        int compressedLength = sb.length();
        for (int i = compressedLength - 1; i >= 1; i--) {
            char curC = sb.charAt(i), prevC = sb.charAt(i - 1);
            if (Character.isDigit(curC) && Character.isLetter(prevC))
                sb.insert(i, ',');
            else if (Character.isLetter(curC) && Character.isDigit(prevC))
                sb.insert(i, ';');
        }
        String[] array = sb.toString().split(";");
        length = array.length;
        letters = new char[length];
        counts = new int[length];
        for (int i = 0; i < length; i++) {
            String letterCount = array[i];
            String[] letterCountArray = letterCount.split(",");
            letters[i] = letterCountArray[0].charAt(0);
            counts[i] = Integer.parseInt(letterCountArray[1]);
        }
        index = 0;
    }
    
    public char next() {
        if (hasNext()) {
            char curChar = letters[index];
            counts[index]--;
            if (counts[index] == 0)
                index++;
            return curChar;
        } else
            return ' ';
    }
    
    public boolean hasNext() {
        return index < length;
    }
}

/**
 * Your StringIterator object will be instantiated and called as such:
 * StringIterator obj = new StringIterator(compressedString);
 * char param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

Another way is lazy loading way, not un-compressing at the constructor step.

So keep variable currentLetter and currentCount. When currentCount is 0, it will trigger a fetch from input string s.subString(0,2) and parse/reload currentLetter and currentCount.

When next(), get currentLetter and currentCount--.

// OJ: https://leetcode.com/problems/design-compressed-string-iterator
// Time: O(1)
// Space: O(1)
class StringIterator {
private:
  string str;
  int index = 0, nextIndex = 0, cnt = 0;
  void load() {
    while (index < str.size() && !cnt) {
      index = nextIndex;
      nextIndex = index + 1;
      while (nextIndex < str.size() && isdigit(str[nextIndex])) cnt = cnt * 10 + str[nextIndex++] - '0';
    }
  }
public:
  StringIterator(string compressedString) : str(compressedString) {
    load();
  }

  char next() {
    if (!hasNext()) return ' ';
    char ans = str[index];
    --cnt;
    load();
    return ans;
  }

  bool hasNext() {
    return index < str.size();
  }
};

class StringIterator:
    def __init__(self, compressedString: str):
        self.d = []
        self.p = 0
        n = len(compressedString)
        i = 0
        while i < n:
            c = compressedString[i]
            x = 0
            i += 1
            while i < n and compressedString[i].isdigit():
                x = x * 10 + int(compressedString[i])
                i += 1
            self.d.append([c, x])

    def next(self) -> str:
        if not self.hasNext():
            return ' '
        ans = self.d[self.p][0]
        self.d[self.p][1] -= 1
        if self.d[self.p][1] == 0:
            self.p += 1
        return ans

    def hasNext(self) -> bool:
        return self.p < len(self.d) and self.d[self.p][1] > 0


# Your StringIterator object will be instantiated and called as such:
# obj = StringIterator(compressedString)
# param_1 = obj.next()
# param_2 = obj.hasNext()

############

class StringIterator(object):

  def __init__(self, compressedString):
    """
    :type compressedString: str
    """
    self.data = compressedString
    self.idx = -1
    self.decodeNext()

  def decodeNext(self):
    self.idx += 1
    if self.idx + 1 < len(self.data):
      self.cur = self.data[self.idx]
      end = self.idx + 1
      while end < len(self.data) and self.data[end].isdigit():
        end += 1
      print
      end
      self.num = int(self.data[self.idx + 1:end])
      self.idx = end - 1

  def next(self):
    """
    :rtype: str
    """
    if self.hasNext():
      ret = self.cur
      self.num -= 1
      if self.num <= 0:
        self.decodeNext()
      return ret
    return " "

  def hasNext(self):
    """
    :rtype: bool
    """
    return self.idx < len(self.data) and self.num > 0

# Your StringIterator object will be instantiated and called as such:
# obj = StringIterator(compressedString)
# param_1 = obj.next()
# param_2 = obj.hasNext()

604 - Design Compressed String Iterator

604. Design Compressed String Iterator (Easy)

Solution 1.

Solution Java

All Problems

All Solutions

Welcome to Subscribe On Youtube

604. Design Compressed String Iterator (Easy)

Solution 1.

Solution Java

All Problems

All Solutions