Design and implement a data structure for a compressed string iterator. 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.
Implement the StringIterator class:
next()
Returns the next character if the original string still has uncompressed characters, otherwise returns a white space.hasNext()
Returns true if there is any letter needs to be uncompressed in the original string, otherwise returns false
.
Example 1:
Input ["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"] [["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []] Output [null, "L", "e", "e", "t", "C", "o", true, "d", true] Explanation StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1"); stringIterator.next(); // return "L" stringIterator.next(); // return "e" stringIterator.next(); // return "e" stringIterator.next(); // return "t" stringIterator.next(); // return "C" stringIterator.next(); // return "o" stringIterator.hasNext(); // return True stringIterator.next(); // return "d" stringIterator.hasNext(); // return True
Constraints:
1 <= compressedString.length <= 1000
compressedString
consists of lower-case an upper-case English letters and digits.compressedString
is in the range [1, 10^9]
100
calls will be made to next
and hasNext
.struct StringIterator {
index: usize,
pairs: Vec<Pair>,
}
#[derive(Debug, PartialEq, Eq, Clone)]
struct Pair {
c: char,
m: usize,
}
impl Pair {
fn new(c: char, m: usize) -> Self {
Pair { c, m }
}
}
impl StringIterator {
fn new(compressed_string: String) -> Self {
let s: Vec<char> = compressed_string.chars().collect();
let n = s.len();
let mut i = 0;
let mut pairs: Vec<Pair> = vec![];
while i < n {
let c = s[i];
i += 1;
let mut m: usize = 0;
while i < n && s[i].is_numeric() {
m *= 10;
m += (s[i] as u8 - b'0') as usize;
i += 1;
}
pairs.push(Pair::new(c, m));
}
StringIterator { index: 0, pairs }
}
fn next(&mut self) -> char {
if self.index == self.pairs.len() {
' '
} else {
let c = self.pairs[self.index].c;
self.pairs[self.index].m -= 1;
if self.pairs[self.index].m == 0 {
self.index += 1;
}
c
}
}
fn has_next(&self) -> bool {
self.index < self.pairs.len()
}
}
#[test]
fn test() {
let mut iterator = StringIterator::new("L1e2t1C1o1d1e1".to_string());
assert_eq!(iterator.next(), 'L');
assert_eq!(iterator.next(), 'e');
assert_eq!(iterator.next(), 'e');
assert_eq!(iterator.next(), 't');
assert_eq!(iterator.next(), 'C');
assert_eq!(iterator.next(), 'o');
assert_eq!(iterator.next(), 'd');
assert_eq!(iterator.has_next(), true);
assert_eq!(iterator.next(), 'e');
assert_eq!(iterator.has_next(), false);
assert_eq!(iterator.next(), ' ');
}