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

解法1：

思路比较好想。用一个count记录当前字符还剩下的个数，另一个用pos记录在compressedString里面扫描到的位置。
要注意的是在判断hasNext的时候要check count！=0
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class StringIterator {
    int pos = 0;
    char prev = ' ';
    int count = 0;
    String data = null;
    public StringIterator(String compressedString) {
        this.data = compressedString;
    }
    public char next() {
        if (!hasNext()) {
            return ' ';
        }
        if (count == 0) {
            prev = data.charAt(pos++);
            int tempCount = 0;
            while (pos < data.length() && Character.isDigit(data.charAt(pos))) {
                tempCount = tempCount * 10 + data.charAt(pos) - '0';
                pos++;
            }
            count = tempCount;
        }
        count--;
        return prev;        
    }
    public boolean hasNext() {
        return pos < data.length() || 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();
 */