LeetCode 604. Design Compressed String Iterator(java)
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.
考え方:まず、私が考えているのは、stackを1つ使って、後ろから前へ、最後に生成した文字をstackに詰め込み、next()とhasNext()のたびにstackからpopが出てくることです.しかし、この方法はleetcodeを越えられない.「a 1038373845 b 1032394854」という例が現れ、時間が非常に遅いので、左からpopごとに-1をカウントし、カウントが0になったら2番目の文字を開始する方法を変えた.以下は2つのメソッドのコードですが、2つ目のメソッドだけがLeetCodeを通過できます.
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 ' '
考え方:まず、私が考えているのは、stackを1つ使って、後ろから前へ、最後に生成した文字をstackに詰め込み、next()とhasNext()のたびにstackからpopが出てくることです.しかし、この方法はleetcodeを越えられない.「a 1038373845 b 1032394854」という例が現れ、時間が非常に遅いので、左からpopごとに-1をカウントし、カウントが0になったら2番目の文字を開始する方法を変えた.以下は2つのメソッドのコードですが、2つ目のメソッドだけがLeetCodeを通過できます.
// :stack
class StringIterator {
Stack stack = new Stack<>();
public StringIterator(String compressedString) {
int count = 1, num = 0, len = compressedString.length();
for (int i = len - 1; i >= 0; i--) {
char c = compressedString.charAt(i);
if (Character.isDigit(c)) {
int end = i;
while (i < len && Character.isDigit(compressedString.charAt(i))) {
i--;
}
i++;
for (int j = i; j <= end; j++) {
num = num * 10 + compressedString.charAt(j) - '0';
if (num > Integer.MAX_VALUE) {
num = Integer.MAX_VALUE;
}
}
count = num;
num = 0;
} else {
for (int j = 0; j < count; j++) {
stack.push(c);
}
count = 1;
}
}
}
public char next() {
return stack.isEmpty() ? ' ' : stack.pop();
}
public boolean hasNext() {
return stack.isEmpty() ? false : true;
}
}
// :
class StringIterator {
char letter;
int count;
int index;
int len;
String s;
public StringIterator(String compressedString) {
s = compressedString;
len = s.length();
index = 0;
helper();
}
public char next() {
if (count > 0) {
count--;
return letter;
} else {
if (index == len) {
return ' ';
} else {
helper();
count--;
return letter;
}
}
}
public boolean hasNext() {
return (index == len && count <= 0) ? false : true;
}
public void helper() {
char c = s.charAt(index);
letter = c;
int num = 0;
while (++index < len && Character.isDigit(s.charAt(index))) {
num = num * 10 + s.charAt(index) - '0';
}
count = num;
}
}