> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/design/604.-design-compressed-string-iterator.md).

# 604. Design Compressed String Iterator

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.

**Note:**\
Please remember to **RESET** your class variables declared in StringIterator, as static/class variables are **persisted across multiple test cases**. Please see [here](https://leetcode.com/faq/#different-output) for more details.

**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 ' '
```

```cpp
class StringIterator {
public:
    StringIterator(string compressedString) {
        int i = 0, n = compressedString.length();
        while (i < n) {
            int j = i + 1;
            while (j < n && compressedString[j] - 'A' < 0) ++j;
            int diff = compressedString[i] - 'A';
            string times = compressedString.substr(i + 1, j - i - 1);
            q.push({diff, stoi(times)});
            i = j;
        }
    }
    
    char next() {
        if (!hasNext()) return ' ';
        vector<int>& t = q.front();
        char ch = t[0] + 'A';
        if (--t[1] == 0) q.pop();
        return ch;
    }
    
    bool hasNext() {
        return !q.empty();
    }
private:
    queue<vector<int> > q;
};
```

```cpp
class StringIterator {
public:
    StringIterator(string compressedString) {
        str = compressedString;
        len = str.length();
        i = 0;
        cnt = 0;
        ch = ' ';
    }
    
    char next() {
        if (hasNext()) {
            --cnt;
            return ch;
        }
        return ' ';
    }
    
    bool hasNext() {
        if (cnt > 0) return true;
        if (i >= len) return false;
        ch = str[i++];
        while (i < len && str[i] >= '0' && str[i] <= '9') {
            cnt = cnt * 10 + str[i++] - '0';
        }
        return true;
    }
private:
    string str;
    int len, i, cnt;
    char ch;
};
```

```cpp
class StringIterator {
public:
    StringIterator(string compressedString) {
        is = istringstream(compressedString);
    }
    
    char next() {
        if (hasNext()) {
            --cnt;
            return ch;
        }
        return ' ';
    }
    
    bool hasNext() {
        if (cnt == 0) {
            is >> ch >> cnt;
        }
        return cnt > 0;
    }
private:
    istringstream is;
    int cnt = 0;
    char ch = ' ';
};
```