604. Design Compressed String Iterator

leetcode easy

#array#backtracking#csharp#design#easy#leetcode#string

Task

Разработайте и реализуйте структуру данных для итератора сжатой строки. Данная сжатая строка будет в виде каждой буквы, за которой следует положительное целое число, представляющее количество этой буквы в оригинальной несжатой строке.

Реализуйте класс

StringIterator

next()

: Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.

hasNext()

: Возвращает

true

, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает

false

Пример:

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 "t"

stringIterator.next(); // return "C"

stringIterator.next(); // return "o"

stringIterator.hasNext(); // return True

stringIterator.next(); // return "d"

stringIterator.hasNext(); // return True

C# solution

matched/original

public class StringIterator {
    private StringBuilder res = new StringBuilder();
    private int ptr = 0;
    public StringIterator(string s) {
        int i = 0;
        while (i < s.Length) {
            char ch = s[i++];
            int num = 0;
            while (i < s.Length && char.IsDigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            for (int j = 0; j < num; j++)
                res.Append(ch);
        }
    }
    public char Next() {
        return !HasNext() ? ' ' : res[ptr++];
    }
    public bool HasNext() {
        return ptr != res.Length;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class StringIterator {
    private StringBuilder res = new StringBuilder();
    private int ptr = 0;
    public StringIterator(string s) {
        int i = 0;
        while (i < s.size()) {
            char ch = s[i++];
            int num = 0;
            while (i < s.size() && char.IsDigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            for (int j = 0; j < num; j++)
                res.Append(ch);
        }
    }
    public char Next() {
        return !HasNext() ? ' ' : res[ptr++];
    }
    public bool HasNext() {
        return ptr != res.size();
    }
}

Java solution

matched/original

public class StringIterator {
    StringBuilder res = new StringBuilder();
    int ptr = 0;

    public StringIterator(String s) {
        int i = 0;
        while (i < s.length()) {
            char ch = s.charAt(i++);
            int num = 0;
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
                i++;
            }
            for (int j = 0; j < num; j++)
                res.append(ch);
        }
    }

    public char next() {
        return !hasNext() ? ' ' : res.charAt(ptr++);
    }

    public boolean hasNext() {
        return ptr != res.length();
    }
}

JavaScript solution

matched/original

class StringIterator {
    constructor(s) {
        this.res = [];
        this.ptr = 0;
        let i = 0;
        while (i < s.length) {
            let ch = s[i++];
            let num = 0;
            while (i < s.length && !isNaN(s[i])) {
                num = num * 10 + parseInt(s[i]);
                i++;
            }
            this.res.push(...Array(num).fill(ch));
        }
    }

    next() {
        return this.hasNext() ? this.res[this.ptr++] : ' ';
    }

    hasNext() {
        return this.ptr < this.res.length;
    }
}

Python solution

matched/original

class StringIterator:
    def __init__(self, s: str):
        self.res = []
        self.ptr = 0
        i = 0
        while i < len(s):
            ch = s[i]
            i += 1
            num = 0
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            self.res.extend([ch] * num)

    def next(self) -> str:
        if not self.hasNext():
            return ' '
        char = self.res[self.ptr]
        self.ptr += 1
        return char

    def hasNext(self) -> bool:
        return self.ptr < len(self.res)

Go solution

matched/original

package main

type StringIterator struct {
    res []rune
    ptr int
}

func Constructor(s string) StringIterator {
    res := []rune{}
    i := 0
    for i < len(s) {
        ch := rune(s[i])
        i++
        num := 0
        for i < len(s) && s[i] >= '0' && s[i] <= '9' {
            num = num*10 + int(s[i]-'0')
            i++
        }
        for j := 0; j < num; j++ {
            res = append(res, ch)
        }
    }
    return StringIterator{res: res, ptr: 0}
}

func (this *StringIterator) Next() rune {
    if !this.HasNext() {
        return ' '
    }
    ch := this.res[this.ptr]
    this.ptr++
    return ch
}

func (this *StringIterator) HasNext() bool {
    return this.ptr < len(this.res)
}

Explanation

Algorithm

Предварительная обработка

Мы заранее создаем несжатую строку. Для этого проходим по данному сжатому строковому представлению и добавляем несжатые буквы для каждой сжатой буквы в результирующий строковый строитель res. Чтобы найти количество несжатых букв, мы проходим по данному сжатому строковому представлению. Когда находим букву, определяем следующее за ней число, используя десятичную арифметику. Таким образом, получаем два элемента (букву и количество), необходимые для формирования текущего фрагмента несжатой строки.

Операция next()

Начинаем с проверки, есть ли еще несжатые буквы в строке. Если нет, hasNext() возвращает False, а next() возвращает пробел (' '). В противном случае возвращаем букву, на которую указывает ptr, указывающий на следующую букву для возврата. Перед возвратом буквы также обновляем ptr, чтобы указывать на следующую букву в res.

Операция hasNext()

Если указатель ptr выходит за пределы массива res, это указывает на то, что больше несжатых букв нет. В этом случае возвращаем False. В противном случае возвращаем True.

😎