Welcome to Subscribe On Youtube

604. Design Compressed String Iterator

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 <= 1000
  • compressedString 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

Class StringIterator

__init__ Method

  • Parameters: Takes compressedString, a string where each letter is followed by a positive integer indicating the number of times the letter appears consecutively.
  • Logic:
    • The method initializes an empty list self.d to store pairs [character, count].
    • self.p is initialized to 0 and will serve as a pointer to the current element in self.d.
    • It then iterates over compressedString to extract each character and its corresponding count. This is achieved using a nested loop where the outer loop picks the character and the inner loop computes the count (which may have more than one digit).

next Method

  • Functionality: Returns the next character in the uncompressed version of the string.
  • Logic:
    • First, it checks if there are any characters left using hasNext(). If none, it returns a space ' '.
    • It retrieves the current character (ans) from self.d[self.p][0].
    • Decrements the count of this character by 1.
    • If the count of the current character becomes 0, it increments the pointer self.p to move to the next character.
    • Returns ans, the current character.

hasNext Method

  • Functionality: Checks if there are more characters to return.
  • Logic:
    • Returns True if self.p is less than the length of self.d and the count of the current character (self.d[self.p][1]) is greater than 0. Otherwise, returns False.
  • 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();
     */
    
  • 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();
     */
    
  • '''
    Lazy Evaluation: Characters are processed and returned on-demand, 
    which can be advantageous for large data or in scenarios where the entire string might not be needed.
    '''
    class StringIterator: # more memory-efficient
        def __init__(self, compressedString: str):
            self.compressedString = compressedString
            self.index = 0
            self.currentChar = None
            self.charCount = 0
            self.n = len(compressedString)
    
        '''
            This private method updates the currentChar and charCount to the next character 
            and its count in the compressed string. 
            It's called when the current character count reaches zero.
        '''
        def _updateNextChar(self):
            if self.index < self.n:
                self.currentChar = self.compressedString[self.index]
                self.index += 1
                self.charCount = 0
                while self.index < self.n and self.compressedString[self.index].isdigit():
                    self.charCount = self.charCount * 10 + int(self.compressedString[self.index])
                    self.index += 1
            else:
                self.currentChar = ' '
                self.charCount = 0
    
        def next(self) -> str:
            if self.charCount == 0:
                self._updateNextChar()
            if self.charCount > 0:
                self.charCount -= 1
                return self.currentChar
            return ' '
    
        def hasNext(self) -> bool:
            return self.index < self.n or self.charCount > 0
    
    ##########
    
    class StringIterator:
        def __init__(self, compressedString: str):
            self.d = []
            self.p = 0
            n = len(compressedString)
            i = 0
            while i < n: # just flat it right away
                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()
    
    
  • 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();
     */
    

All Problems

All Solutions