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();
*/
网友评论