[LintCode] 604. Design Compressed String Iterator

alin 發(fā)布于2019-08-16 13:34 / 561人閱讀

Problem

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

class StringIterator {
    Queue queue;
    public StringIterator(String str) {
        queue = new LinkedList<>();
        int i = 0, len = str.length();
        while (i < len) {
            int j = i+1;
            while (j < len && Character.isDigit(str.charAt(j))) j++;
            
            char ch = str.charAt(i);
            int count = Integer.parseInt(str.substring(i+1, j));
            queue.offer(new Node(ch, count));
            
            i = j;
        }
    }
    public char next() {
        if (!hasNext()) return " ";
        Node node = queue.peek();
        node.count--;
        if (node.count == 0) queue.poll();
        return node.val;
    }
    public boolean hasNext() {
        return !queue.isEmpty();
    }
}
class Node {
    char val;
    int count;
    public Node(char c, int n) {
        this.val = c;
        this.count = n;
    }
}