Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/604.html
604. Design Compressed String Iterator (Easy)
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.
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
In the constructor, split out each term that is a (character, count) pair. Then for each pair, split out the character and the count. Use two arrays to store the letters and the corresponding counts respectively. Both arrays have the same length. Initialize the index to 0.
For next
operation, if there exists a next character, then obtain the character at the index as the return value, decrease the count at the index by 1. If the count at the index becomes 0 after decreasing, move to the next index. Return the character which is the return value. If there doesn’t exist a next character, return a space.
For hasNext
operation, simply return whether the index is less than the length of both arrays.
-
class StringIterator { char[] letters; int[] counts; int length; int index; public StringIterator(String compressedString) { StringBuffer sb = new StringBuffer(compressedString); int compressedLength = sb.length(); for (int i = compressedLength - 1; i >= 1; i--) { char curC = sb.charAt(i), prevC = sb.charAt(i - 1); if (Character.isDigit(curC) && Character.isLetter(prevC)) sb.insert(i, ','); else if (Character.isLetter(curC) && Character.isDigit(prevC)) sb.insert(i, ';'); } String[] array = sb.toString().split(";"); length = array.length; letters = new char[length]; counts = new int[length]; for (int i = 0; i < length; i++) { String letterCount = array[i]; String[] letterCountArray = letterCount.split(","); letters[i] = letterCountArray[0].charAt(0); counts[i] = Integer.parseInt(letterCountArray[1]); } index = 0; } public char next() { if (hasNext()) { char curChar = letters[index]; counts[index]--; if (counts[index] == 0) index++; return curChar; } else return ' '; } public boolean hasNext() { return index < length; } } /** * 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(); */
Another way is lazy loading way, not un-compressing at the constructor step.
So keep variable
currentLetter
andcurrentCount
. WhencurrentCount
is 0, it will trigger a fetch from input strings.subString(0,2)
and parse/reloadcurrentLetter
andcurrentCount
.When
next()
, getcurrentLetter
andcurrentCount--
. -
// OJ: https://leetcode.com/problems/design-compressed-string-iterator // Time: O(1) // Space: O(1) class StringIterator { private: string str; int index = 0, nextIndex = 0, cnt = 0; void load() { while (index < str.size() && !cnt) { index = nextIndex; nextIndex = index + 1; while (nextIndex < str.size() && isdigit(str[nextIndex])) cnt = cnt * 10 + str[nextIndex++] - '0'; } } public: StringIterator(string compressedString) : str(compressedString) { load(); } char next() { if (!hasNext()) return ' '; char ans = str[index]; --cnt; load(); return ans; } bool hasNext() { return index < str.size(); } };
-
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() ############ class StringIterator(object): def __init__(self, compressedString): """ :type compressedString: str """ self.data = compressedString self.idx = -1 self.decodeNext() def decodeNext(self): self.idx += 1 if self.idx + 1 < len(self.data): self.cur = self.data[self.idx] end = self.idx + 1 while end < len(self.data) and self.data[end].isdigit(): end += 1 print end self.num = int(self.data[self.idx + 1:end]) self.idx = end - 1 def next(self): """ :rtype: str """ if self.hasNext(): ret = self.cur self.num -= 1 if self.num <= 0: self.decodeNext() return ret return " " def hasNext(self): """ :rtype: bool """ return self.idx < len(self.data) and self.num > 0 # Your StringIterator object will be instantiated and called as such: # obj = StringIterator(compressedString) # param_1 = obj.next() # param_2 = obj.hasNext()
-
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(); */