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

The Idea: I took an old C approach using a pointer. The general idea is to maintain an iterator for the compressed string, and only increment it when nessessary. The constructor begins by exposing the current character and the digits that follow. It will always follow that these digits are always one index ahead of the current iterator. Next(): returns the current character at the iterator and decrements the identified compressed digits. When the digit is 0, it increments to the next character (by adding the length of the previous compressed bit), and then identifies the next set of digits. hasNext(): Will always return true unless the iterate exceeds the bounds of the string.

Complexity: O(1) time and space

class StringIterator {
public:
    StringIterator(string compressedString) {
        comp_str = compressedString;
        iter = 0;
        dist = new int();
        if (!comp_str.empty()) {
            cur_uncomp = get_next_digit(iter + 1, dist);
        }
    }

    char next() {
        if (iter + 1 < comp_str.size()) {
            char ret = comp_str[iter];
            cur_uncomp--;
            if (cur_uncomp == 0) {
                iter += *dist + 1;
                cur_uncomp = get_next_digit(iter + 1, dist);
            }
            return ret;
        }
        else return ' ';
    }

    bool hasNext() {
        return (iter + 1 < comp_str.size());
    }

    int *dist;
    int cur_uncomp;
    string comp_str;
    int iter;

    int get_next_digit(int start, int *&dist) {
        string cum_digits = "";
        int start_cp = start;
        while (start < comp_str.size()
            && isdigit(comp_str[start])) {
            cum_digits += comp_str[start++];
        }
        *dist = start - start_cp;
        return atoi(cum_digits.c_str());
    }
};