Design Compressed String Iterator

šŸ  ā¬…ļø āž”ļø

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.
Note: This problem is from LeetCode.
āŒ Compiled
āŒ Executed
āŒ Correct 
program main
    use StringIterator_mod
    implicit none

    type(StringIterator) :: stringIterator
    character(len=:), allocatable :: nextChar
    logical :: hasNext

    ! Examples
    call stringIterator%init("L1e2t1C1o1d1e1")
    do while (stringIterator%hasNext())
        nextChar = stringIterator%next()
        write (*, "(A)", advance="no") trim(nextChar)
    end do
    write (*, *)

    call stringIterator%init("")
    do while (stringIterator%hasNext())
        nextChar = stringIterator%next()
        write (*, "(A)", advance="no") trim(nextChar)
    end do
    write (*, *)

contains

    subroutine init(this, compressedString)
        class(StringIterator), intent(inout) :: this
        character(len=*), intent(in) :: compressedString

        this%compressedString = compressedString
        this%index = 1
    end subroutine init

    function next(this) result(res)
        class(StringIterator), intent(inout) :: this
        character(len=1), allocatable :: res

        if (this%index > len(this%compressedString)) then
            res = ' '
        else
            read (this%compressedString(this%index:), fmt='(A)', iostat=ioStatus) res
            this%index = this%index + len(res) + 1
        end if
    end function next

    function hasNext(this) result(res)
        class(StringIterator), intent(inout) :: this
        logical :: res

        res = this%index <= len(this%compressedString)
    end function hasNext
end program main

module StringIterator_mod
    implicit none

    private
    public :: StringIterator

    type :: StringIterator
        character(len=:), allocatable :: compressedString
        integer :: index
    contains
        procedure :: init => init
        procedure :: next => next
        procedure :: hasNext => hasNext
    end type StringIterator

contains

    subroutine init(this, compressedString)
        class(StringIterator), intent(inout) :: this
        character(len=*), intent(in) :: compressedString

        this%compressedString = compressedString
        this%index = 1
    end subroutine init

    function next(this) result(res)
        class(StringIterator), intent(inout) :: this
        character(len=1), allocatable :: res

        if (this%index > len(this%compressedString)) then
            res = ' '
        else
            read (this%compressedString(this%index:), fmt='(A)', iostat=ioStatus) res
            this%index = this%index + len(res) + 1
        end if
    end function next

    function hasNext(this) result(res)
        class(StringIterator), intent(inout) :: this
        logical :: res

        res = this%index <= len(this%compressedString)
    end function hasNext
end module StringIterator_mod
āŒ Compiled
āŒ Executed
āŒ Correct 
! Declare the data structure for the compressed string iterator
type StringIterator
    ! Private variables
    integer :: index = 1
    character(len=1) :: current_char = ' '
    character(len=1) :: next_char = ' '
    integer :: count = 0
    logical :: has_next = .false.

    ! Private methods
    contains
        ! Advance the iterator to the next character
        subroutine advance()
            integer :: i

            ! If the current character is not a space, increment the count
            if (current_char /= ' ') then
                count = count + 1
            end if

            ! If the count is greater than 0, decrement the count
            if (count > 0) then
                count = count - 1
            end if

            ! If the count is 0, advance to the next character
            if (count == 0) then
                index = index + 1
                if (index <= len(compressed_string)) then
                    current_char = compressed_string(index:index)
                    count = 1
                else
                    current_char = ' '
                end if
            end if
        end subroutine advance

        ! Check if there are any more characters to be uncompressed
        function has_next() result(has_next)
            logical :: has_next

            ! If the current character is not a space, or the count is greater than 0,
            ! then there are still characters to be uncompressed
            if (current_char /= ' ' .or. count > 0) then
                has_next = .true.
            else
                has_next = .false.
            end if
        end function has_next

        ! Return the next character
        function next() result(next_char)
            character(len=1) :: next_char

            ! If there are still characters to be uncompressed, advance the iterator
            if (has_next()) then
                call advance()
            end if

            ! Return the next character
            next_char = current_char
        end function next
end type StringIterator

! Declare the main program
program main
    ! Declare the variables
    type(StringIterator) :: string_iterator
    character(len=1) :: next_char
    logical :: has_next

    ! Create a new string iterator
    string_iterator = StringIterator(compressed_string="L1e2t1C1o1d1e1 ")

    ! Loop until there are no more characters to be uncompressed
    do while (string_iterator%has_next())
        ! Get the next character
        next_char = string_iterator%next()

        ! Print the next character
        write (*,*) next_char
    end do
end program main

! Declare the compressed string
character(len=1), parameter :: compressed_string = "L1e2t1C1o1d1e1 "

! Declare the main entry point
entry main

! Call the main program
call main

! End of file
end
šŸŒ Data from online sources 
class StringIterator:
    def __init__(self, compressedString: str):
        self.s = compressedString
        self.i = 0
        self.count = 0
        self.ch = " "

    def next(self) -> str:
        if not self.hasNext():
            return " "
        if self.count == 0:
            self.ch = self.s[self.i]
            self.i += 1
            while self.i < len(self.s) and self.s[self.i].isdigit():
                self.count = self.count * 10 + int(self.s[self.i])
                self.i += 1
        self.count -= 1
        return self.ch

    def hasNext(self) -> bool:
        return self.i < len(self.s) or self.count != 0

The main idea of the algorithm is to iterate through the compressed string, extracting each character and its associated count of repetitions. Each extracted character is stored in 'ch' and its count of repetitions is stored in 'count'. The 'next()' function checks if there are still letters to uncompress - if there aren't, it returns a white space. The 'next()' function also checks if the current count of repetitions for the character 'ch' is 0 - if it is, it extracts the next character from the compressed string until it encounters a digit, then extracts the whole count value. The 'hasNext()' function checks if there are any more characters in the compressed string or if the count of repetitions is not 0, meaning there are still characters to be uncompressed.
šŸŒ Data from online sources 
#include <string>
class StringIterator {
public:
    StringIterator(const std::string& compressedString) {
        s = compressedString;
        i = 0;
        count = 0;
        ch = ' ';
    }
    char next() {
        if(!hasNext()) return ' ';
        if(count == 0) {
            ch = s[i++];
            while(i < s.size() && isdigit(s[i])) {
                count = count * 10 + (s[i++] - '0');
            }
        }
        count--;
        return ch;
    }
    bool hasNext() {
        return i < s.size() || count != 0;
    }
private:
    std::string s;
    int i;
    int count;
    char ch;
};

The main idea of the algorithm is to iterate through the compressed string, extracting each character and its associated count of repetitions. Each extracted character is stored in 'ch' and its count of repetitions is stored in 'count'. The 'next()' function checks if there are still letters to uncompress - if there aren't, it returns a white space. The 'next()' function also checks if the current count of repetitions for the character 'ch' is 0 - if it is, it extracts the next character from the compressed string until it encounters a digit, then extracts the whole count value. The 'hasNext()' function checks if there are any more characters in the compressed string or if the count of repetitions is not 0, meaning there are still characters to be uncompressed.