LeetCode: Design Compressed String Iterator

LeetCode: 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.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
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
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
40
41
42
43
44
45
46
47
48
49
public class StringIterator {

private long cursor = 0;
private long size = 0;
private Map<Long, Character> map = new HashMap<>();

public StringIterator(String compressedString) {
char pre = ' ';
long crt = 0;
for (char c : compressedString.toCharArray()) {
if (c >= '0' && c <= '9') {
crt = 10 * crt + c - '0';
} else {
size += crt;
if (pre != ' ') map.put(size, pre);
pre = c;
crt = 0;
}
}
if (crt > 0) {
size += crt;
map.put(size, pre);
}
}

public char next() {
if (cursor >= size) return ' ';

long key = map.keySet().stream()
.filter(x -> x > cursor)
.mapToLong(Long::longValue)
.min()
.orElse(0);
cursor++;
return map.get(key);
}

public boolean hasNext() {
return cursor < size;
}

}

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