Design Compressed String Iterator

Problem

Design and implement a data structure for a compressed string iterator. 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.

Implement the StringIterator class:

• next() Returns the next character if the original string still has uncompressed characters, otherwise returns a white space.
• hasNext() Returns true if there is any letter needs to be uncompressed in the original string, otherwise returns false.

Constraints

• 1 <= compressedString.length <= 1000
• compressedString consists of lower-case an upper-case English letters and digits.
• The number of a single character repetitions in compressedString is in the range [1, 109].
• At most 100 calls will be made to next and hasNext.

Solution

The problem Design Compressed String Iterator can be solved by creating vector of characters and the number of repetitions from the given string.

Implementation

class StringIterator
{
  private:
    vector<char> ch;
    vector<int> count;

  public:
    StringIterator(string compressedString)
    {
        string num;
        for (int i = compressedString.length() - 1; i >= 0; i--)
        {
            if (isdigit(compressedString[i]))
                num += compressedString[i];
            else
            {
                ch.push_back(compressedString[i]);
                count.push_back(stoi(string(num.rbegin(), num.rend())));
                num = "";
            }
        }
    }

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

        char ret = ch.back();
        count.back() -= 1;

        if (count.back() == 0)
        {
            ch.pop_back();
            count.pop_back();
        }

        return ret;
    }

    bool hasNext() { return ch.size(); }
};

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