Problem Explanation

The problem involves designing a data structure that decodes a compacted string. The given string is in a format where each alphabet is followed by a count integer that represents how many times the alphabet occurs in the original string.

Let's walk through an example. Suppose we have a compressed string L3e2t1f1d1e1, then the uncompressed string is LLLeeftfdee.

The data structure needs to support two operations:

• next(): it should return the next alphabet if there are uncompressed characters or return an empty space.

• hasNext(): checks if there are any more letters to be uncompressed.

Solution Explanation

The implemented class StringIterator saves the compressed string in global scope. There are also integers to track the current index in the string, the count of the current alphabet, and a variable for the current alphabet.

The next() function returns a white space if there no more characters to be uncompressed. Otherwise, it checks if the count of current alphabet is 0. If it is, it assigns the alphabet at the current index to the currentChar and adds up the counts. It then decrements the count of the current alphabet and returns it.

The hasNext() function returns a boolean that shows if there are more characters to be uncompressed. It checks if the current index is less than the length of the string or there are more of the current alphabet to go.

Algorithm Steps

1. Initialize an object of class StringIterator with the compressed string. Assign current alphabet as empty. Current count and index to be 0.

2. When next() is called, first check if hasNext() is false, return " ". If num is 0, update the current alphabet and its count. Decrease the count and return the current alphabet.

3. When hasNext() is called, if there are still characters left in the string or the count of the current alphabet is more than 0, return true. Return false otherwise.

Java

1
2java
3class StringIterator {
4    String res;
5    int ptr = 0, num = 0;
6    char ch = ' ';
7    
8    public StringIterator(String s) {
9        res = s;
10    }
11
12    public char next() {
13        if (!hasNext()) {
14            return ' ';
15        }
16        if (num == 0) {
17            ch = res.charAt(ptr++);
18            while (ptr < res.length() && Character.isDigit(res.charAt(ptr))) {
19                num = num * 10 + res.charAt(ptr++) - '0';
20            }
21        }
22        num--;
23        return ch;
24    }
25
26    public boolean hasNext() {
27        return ptr != res.length() || num != 0;
28    }
29}

Python

1
2python
3class StringIterator:
4
5    def __init__(self, compressedString: str):
6        self.s = compressedString
7        self.i = 0
8        self.num = 0
9        self.ch = ' '
10
11    def next(self) -> str:
12        if not self.hasNext():
13            return ' '
14        if self.num == 0:
15            self.ch = self.s[self.i]
16            self.i += 1
17            while self.i < len(self.s) and '0'<= self.s[self.i] <= '9':
18                self.num = self.num * 10 + int(self.s[self.i])
19                self.i += 1
20        self.num -= 1
21        return self.ch
22
23    def hasNext(self) -> bool:
24        return self.i != len(self.s) or self.num != 0

JavaScript

1
2javascript
3var StringIterator = function(compressedString) {
4    this.s = compressedString;
5    this.i = 0;
6    this.num = 0;
7    this.ch = ' ';
8};
9
10StringIterator.prototype.next = function() {
11    if (!this.hasNext()) {
12        return ' ';
13    }
14    if (this.num === 0) {
15        this.ch = this.s[this.i];
16        this.i += 1;
17        while (this.i < this.s.length && '0'<= this.s[this.i] && this.s[this.i] <= '9') {
18            this.num = this.num * 10 + parseInt(this.s[this.i]);
19            this.i += 1;
20        }
21    }
22    this.num -= 1;
23    return this.ch;
24};
25
26StringIterator.prototype.hasNext = function() {
27    return this.i !== this.s.length || this.num !== 0;
28};

C#

1
2csharp
3public class StringIterator {
4    string str;
5    int ptr = 0, num = 0;
6    char ch = ' ';
7    
8    public StringIterator(string compressedString) {
9        str = compressedString;
10    }
11
12    public char Next() {
13        if (!HasNext()) {
14            return ' ';
15        }
16        if (num == 0) {
17            ch = str[ptr++];
18            while (ptr < str.Length && Char.IsDigit(str[ptr])) {
19                num = num * 10 + str[ptr++] - '0';
20            }
21        }
22        num--;
23        return ch;
24    }
25
26    public bool HasNext() {
27        return ptr != str.Length || num != 0;
28    }
29}

C++

1
2cpp
3class StringIterator {
4public:
5    StringIterator(string compressedString) : s(compressedString), i(0), num(0), ch(' ') {}
6    char next() {
7        if (!hasNext())
8            return ' ';
9        if (num == 0) {
10            ch = s[i++];
11            while (i < s.length() && isdigit(s[i]))
12                num = num * 10 + (s[i++] - '0');
13        }
14        num--;
15        return ch;
16    }
17    bool hasNext() {
18        return i < s.length() || num > 0;
19    }
20
21private:
22    const string s;
23    int i, num;
24    char ch;
25};

With these pieces of code, you are able to iterate through a compressed string in languages such as Python, JavaScript, Java, C#, and C++. Notably, use Character.isDigit() in Java, isdigit() in C++, and '0'<= this.s[this.i] <= '9' in Python and JavaScript checks whether a character is a digit.# Kotlin

1
2kotlin
3class StringIterator(compressedString: String) {
4    private var res = compressedString
5    private var ptr = 0
6    private var num = 0
7    private var ch = ' '
8
9    fun next(): Char {
10        if (!hasNext()) {
11            return ' '
12        }
13        if (num == 0) {
14            ch = res[ptr++]
15            while (ptr < res.length && Character.isDigit(res[ptr])) {
16                num = num * 10 + res[ptr++] - '0'
17            }
18        }
19        num--
20        return ch
21    }
22
23    fun hasNext(): Boolean {
24        return ptr != res.length || num != 0
25    }
26}

Swift

1
2swift
3class StringIterator {
4    var s: String
5    var i, num: Int
6    var ch: Character
7    
8    init(_ compressedString: String) {
9        self.s = compressedString
10        self.i = 0
11        self.num = 0
12        self.ch = " "
13    }
14
15    func next() -> Character {
16        if !hasNext() {
17            return " "
18        }
19        if num == 0 {
20            ch = s[s.index(s.startIndex, offsetBy: i)]
21            i += 1
22            while i < s.count && s[s.index(s.startIndex, offsetBy: i)].isNumber {
23                num = num * 10 + Int(String(s[s.index(s.startIndex, offsetBy: i)]))!
24                i += 1
25            }
26        }
27        num -= 1
28        return ch
29    }
30
31    func hasNext() -> Bool {
32        return i != s.count || num != 0
33    }
34}

Ruby

1
2ruby
3class StringIterator
4    def initialize(compressedString)
5        @s = compressedString
6        @i = 0
7        @num = 0
8        @ch = ' '
9    end
10
11    def next()
12        return ' ' if !has_next()
13        if @num == 0
14            @ch = @s[@i]
15            @i += 1
16            while @i < @s.length && (0..9).include?(@s[@i].to_i)
17                @num = @num * 10 + @s[@i].to_i
18                @i += 1
19            end
20        end
21        @num -= 1
22        return @ch
23    end
24
25    def has_next()
26        return @i != @s.length || @num != 0
27    end
28end

Php

1
2php
3class StringIterator {
4    private $s, $num = 0, $i = 0;
5    private $ch = "";
6
7    public function __construct(string $compressedString) {
8        $this->s = $compressedString;
9    }
10
11    public function next() {
12        if (!$this->hasNext()) {
13            return "";
14        }
15        if ($this->num === 0) {
16            $this->ch = $this->s[$this->i];
17            $this->i += 1;
18            while ($this->i < strlen($this->s) && is_numeric($this->s[$this->i])) {
19                $this->num = $this->num * 10 + $this->s[$this->i];
20                $this->i += 1;
21            }
22        }
23        $this->num -= 1;
24        return $this->ch;
25    }
26
27    public function hasNext() {
28        return $this->i !== strlen($this->s) || $this->num !== 0;
29    }
30}

These are the solutions of our problem Design Compressed String Iterator in multiple languages like Kotlin, Swift, Ruby, and Php. In summary, regardless of the language, the solution uses variables for the iterations through the string, count of current character, the current character itself, and, if necessary a function to check if a character is a digit. Although the syntaxes may slightly differ per language, the logic remains the same for this problem.