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 ' '
**
class StringIterator {
ArrayList<Long> cnt = new ArrayList<>();
ArrayList<Character> chars = new ArrayList<>();
int count = 0; //use count to specify how many chars have been iterated
int pos = 0; //use position to specify the position of chars that needs to be returned
public StringIterator(String compressedString) {
char[] str = compressedString.toCharArray();
//use time to mark which char I am calculating in this while loop
int time = 0;
//use slow to mark the char, and fast pointer to mark the char I am exploring
int slow = 0, fast = 0;
while(fast < str.length) {
//each while loop focuses on solving one char and calculating one char's length
cnt.add((long)0);
chars.add(str[slow]);
fast++;
while (fast < str.length && str[fast] < 58 && str[fast] > 47) {
cnt.set(time, cnt.get(time)*10+str[fast++]-'0');
}
if(fast<str.length) {
slow = fast;
time++;
}
}
for(int i = 1; i < cnt.size(); i++) {
cnt.set(i, cnt.get(i)+cnt.get(i-1));
}
for(char c: chars) {
System.out.println(c);
}
}
public char next() {
if(hasNext()) {
count++;
if(count > cnt.get(pos)) {
return chars.get(++pos);
}else{
return chars.get(pos);
}
}
return ' ';
}
public boolean hasNext() {
return (count < cnt.get(cnt.size()-1));
}
}
/**
* 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();
*/
Performance Analysis
- The space required for storing the results of the precomputation is O(n)O(n), where nn refers to the length of the compressed string. The numsnums and charschars array contain a total of nn elements.
- The precomputation step requires O(n)O(n) time. Thus, if
hasNext()operation is performed most of the times, this precomputation turns out to be non-advantageous. - Once the precomputation has been done,
hasNext()andnext()requires O(1)O(1) time. - This approach can be extended to include the
previous()andhasPrevious()operations, but that would require making some simple modifications to the current implementation.
Approach #3 Demand-Computation [Accepted]
Algorithm
In this approach, we don't make use of regex for finding the individual components of the given compressedStringcompressedString. We do not perform any form of precomputation. Whenever an operation needs to be performed, the required results are generated from the scratch. Thus, the operations are performed only on demand.
Let's look at the implementation of the required operations:
-
next(): We make use of a global pointer ptrptr to keep a track of which compressed letter in the compressedStringcompressedString needs to be processed next. We also make use of a global variable numnum to keep a track of the number of instances of the current letter which are still pending. Whenevernext()operation needs to be performed, firstly, we check if there are more uncompressed letters left in the compressedStringcompressedString. If not, we return a ' '. Otherwise, we check if there are more instances of the current letter still pending. If so, we directly decrement the count of instances indicated by numsnums and return the current letter. But, if there aren't more instances pending for the current letter, we update the ptrptr to point to the next letter in the compressedStringcompressedString. We also update the numnum by obtaining the count for the next letter from the compressedStringcompressedString. This number is obtained by making use of decimal arithmetic. -
hasNext(): If the pointer ptrptr has reached beyond the last index of the compressedStringcompressedString and numnum becomes, it indicates that no more uncompressed letters exist in the compressed string. Hence, we return a False in this case. Otherwise, a True value is returned indicating that more compressed letters exist in the compressedStringcompressedString.
public class StringIterator {
String res;
int ptr = 0, num = 0;
char ch = ' ';
public StringIterator(String s) {
res = s;
}
public char next() {
if (!hasNext())
return ' ';
if (num == 0) {
ch = res.charAt(ptr++);
while (ptr < res.length() && Character.isDigit(res.charAt(ptr))) {
num = num * 10 + res.charAt(ptr++) - '0';
}
}
num--;
return ch;
}
public boolean hasNext() {
return ptr != res.length() || num != 0;
}
}
Performance Analysis
- Since no precomputation is done, constant space is required in this case.
- The time required to perform
next()operation is O(1)O(1). - The time required for
hasNext()operation is O(1)O(1). - Since no precomputations are done, and
hasNext()requires only O(1)O(1) time, this solution is advantageous ifhasNext()operation is performed most of the times. - This approach can be extended to include
previous()andhasPrevious()operationsm, but this will require the use of some additional variables.
