Description
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 <= 1000compressedString consists of lower-case an upper-case English letters and digits.- The number of a single character repetitions in
compressedString is in the range [1, 10^9]
- At most
100 calls will be made to next and hasNext.
Solutions
Solution 1: Parsing and Storing
Parse the compressedString into characters c and their corresponding repetition counts x, and store them in an array or list d. Use p to point to the current character.
Then perform operations in next and hasNext.
The initialization time complexity is O(n), and the time complexity of the other operations is O(1). Here, n is the length of compressedString.
PythonJavaC++GoTypeScript
class StringIterator:
def __init__(self, compressedString: str):
self.d = []
self.p = 0
n = len(compressedString)
i = 0
while i < n:
c = compressedString[i]
x = 0
i += 1
while i < n and compressedString[i].isdigit():
x = x * 10 + int(compressedString[i])
i += 1
self.d.append([c, x])
def next(self) -> str:
if not self.hasNext():
return ' '
ans = self.d[self.p][0]
self.d[self.p][1] -= 1
if self.d[self.p][1] == 0:
self.p += 1
return ans
def hasNext(self) -> bool:
return self.p < len(self.d) and self.d[self.p][1] > 0
# Your StringIterator object will be instantiated and called as such:
# obj = StringIterator(compressedString)
# param_1 = obj.next()
# param_2 = obj.hasNext()(code-box)
class StringIterator {
private List<Node> d = new ArrayList<>();
private int p;
public StringIterator(String compressedString) {
int n = compressedString.length();
int i = 0;
while (i < n) {
char c = compressedString.charAt(i);
int x = 0;
while (++i < n && Character.isDigit(compressedString.charAt(i))) {
x = x * 10 + (compressedString.charAt(i) - '0');
}
d.add(new Node(c, x));
}
}
public char next() {
if (!hasNext()) {
return ' ';
}
char ans = d.get(p).c;
if (--d.get(p).x == 0) {
++p;
}
return ans;
}
public boolean hasNext() {
return p < d.size() && d.get(p).x > 0;
}
}
class Node {
char c;
int x;
Node(char c, int x) {
this.c = c;
this.x = x;
}
}
/**
* 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();
*/(code-box)
class StringIterator {
public:
StringIterator(string compressedString) {
int n = compressedString.size();
int i = 0;
while (i < n) {
char c = compressedString[i];
int x = 0;
while (++i < n && isdigit(compressedString[i])) {
x = x * 10 + (compressedString[i] - '0');
}
d.push_back({c, x});
}
}
char next() {
if (!hasNext()) return ' ';
char ans = d[p].first;
if (--d[p].second == 0) {
++p;
}
return ans;
}
bool hasNext() {
return p < d.size() && d[p].second > 0;
}
private:
vector<pair<char, int>> d;
int p = 0;
};
/**
* Your StringIterator object will be instantiated and called as such:
* StringIterator* obj = new StringIterator(compressedString);
* char param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/(code-box)
type pair struct {
c byte
x int
}
type StringIterator struct {
d []pair
p int
}
func Constructor(compressedString string) StringIterator {
n := len(compressedString)
i := 0
d := []pair{}
for i < n {
c := compressedString[i]
x := 0
i++
for i < n && compressedString[i] >= '0' && compressedString[i] <= '9' {
x = x*10 + int(compressedString[i]-'0')
i++
}
d = append(d, pair{c, x})
}
return StringIterator{d, 0}
}
func (this *StringIterator) Next() byte {
if !this.HasNext() {
return ' '
}
ans := this.d[this.p].c
this.d[this.p].x--
if this.d[this.p].x == 0 {
this.p++
}
return ans
}
func (this *StringIterator) HasNext() bool {
return this.p < len(this.d) && this.d[this.p].x > 0
}
/**
* Your StringIterator object will be instantiated and called as such:
* obj := Constructor(compressedString);
* param_1 := obj.Next();
* param_2 := obj.HasNext();
*/(code-box)
class StringIterator {
private d: [string, number][] = [];
private p: number = 0;
constructor(compressedString: string) {
const n = compressedString.length;
let i = 0;
while (i < n) {
const c = compressedString[i];
let x = 0;
i++;
while (i < n && !isNaN(Number(compressedString[i]))) {
x = x * 10 + Number(compressedString[i]);
i++;
}
this.d.push([c, x]);
}
}
next(): string {
if (!this.hasNext()) {
return ' ';
}
const ans = this.d[this.p][0];
this.d[this.p][1]--;
if (this.d[this.p][1] === 0) {
this.p++;
}
return ans;
}
hasNext(): boolean {
return this.p < this.d.length && this.d[this.p][1] > 0;
}
}
/**
* Your StringIterator object will be instantiated and called as such:
* var obj = new StringIterator(compressedString)
* var param_1 = obj.next()
* var param_2 = obj.hasNext()
*/(code-box)
