Description

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

Solution

Demand-Computation, hasNext O(1), next O(1), S(1)

维护几个变量，在constructor以及hasNext()中更新current char and count，那么next()可以直接返回。

class StringIterator {
    private String s;
    private int index;
    private char next;
    private int count;

    public StringIterator(String compressedString) {
        s = compressedString;
        index = 0;
        count = 0;
        readNext();
    }
    
    private void readNext() {
        // return directly if current char not eat up or no char left
        if (count > 0 || index >= s.length()) {
            return;
        }
        
        readChar();
        readNum();
    }
    
    private void readChar() {
        next = s.charAt(index++);
    }
    
    private void readNum() {
        while (index < s.length() && Character.isDigit(s.charAt(index))) {
            count = 10 * count + s.charAt(index++) - '0';// increase index
        }
    }
    
    public char next() {
        if (!hasNext()) {
            return ' ';
        }
        
        --count;    // count down here
        return next;
    }
    
    public boolean hasNext() {
        readNext();
        return count > 0;
    }
}

/**
 * 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();
 */