String Compression

Q: Jaka jest złożoność czasowa kompresji ciągów znaków?

Przejście z użyciem dwóch wskaźników zajmuje O(n) czasu, ponieważ indeks skanowania przesuwa się tylko do przodu. Oprócz wyniku przechowuje dwa indeksy, więc dodatkowe zużycie pamięci wynosi O(1) .

ŁatweDwa wskaźniki Tablice i napisy

+10

Otrzymujesz ciąg s złożony z angielskich liter. Skompresuj go: zastąp każdy ciąg dwóch lub więcej takich samych liter występujących po sobie tą literą, po której podaj długość ciągu, a pojedynczą literę pozostaw bez zmian. Zatem aabccc staje się a2bc3. Zwróć skompresowany ciąg.

Wielkie i małe litery są różnymi literami: aA to dwa ciągi o długości 1.

Funkcja

compress(s: string) → string

sstring: ciąg znaków do skompresowania, wyłącznie litery angielskie
Zwracastring: skompresowany ciąg, w którym każda sekwencja jest zapisana jako jej litera, a jeśli jej długość jest większa niż 1, także jako jej długość

Ograniczenia

1 ≤ s.length ≤ 2 × 10⁴
s zawiera wyłącznie angielskie litery, od a do z oraz od A do Z.
Długość serii zapisuje się w systemie dziesiętnym i może składać się z kilku cyfr.

Przykłady

Wejście: s = "aabccc"
Wyjście: "a2bc3"
Wyjaśnienie: Ciągi to aa, b i ccc. Zmieniają się w a2, b (pojedyncza litera nie dostaje liczby) i c3.

Wejście: s = "abbbbbbbbbbbb"
Wyjście: "ab12"
Wyjaśnienie: Jedno a, a potem dwanaście b. Długość 12 zapisujemy za pomocą dwóch znaków 1 i 2, więc wynikiem jest ab12.

Wejście: s = "zzZZZ"
Wyjście: "z2Z3"
Wyjaśnienie: Mała litera z i wielka litera Z to różne litery, więc jest to seria dwóch, po której następuje seria trzech: z2Z3.

Pytanie dodatkowe

Napisz odwrotną operację: mając skompresowany ciąg znaków, taki jak ab12, odtwórz oryginał. Jak odczytać liczbę składającą się z kilku cyfr?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Znajdź początek i koniec każdego ciągu takich samych liter, a następnie zapisz jego długość jako tekst. Ciąg składający się z jednej litery nie otrzymuje liczby, a liczba może mieć kilka cyfr. Dwa indeksy — jeden na początku ciągu, a drugi przesuwający się do jego końca — wykonują to w jednym przebiegu.

Zbierz przebiegi, a następnie je zapisz

Intuicja

Najpierw zapisz serie jako pary litery i długości: dla aabccc będą to (a, 2), (b, 1), (c, 3). Każda litera albo wydłuża ostatnią serię, albo rozpoczyna nową. Następnie zapisz literę każdej serii, a po niej jej długość, jeśli jest większa niż 1.

Oba przebiegi mają złożoność O(n). Lista może zawierać n serii, jeśli żadne dwa sąsiednie znaki nie są takie same, więc wymaga to dodatkowej pamięci O(n).

Algorytm

Utwórz pustą listę serii.
Dla każdej litery w s: jeśli ostatnia seria zawiera tę samą literę, zwiększ jej długość o 1; w przeciwnym razie dodaj nową serię o długości 1.
Dla każdej serii zapisz jej literę, a następnie jej długość w postaci liczby dziesiętnej, jeśli długość jest większa niż 1.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

Dwa wskaźniki dla każdego ciągu

Intuicja

Ustaw i na pierwszej literze bieżącego ciągu i przesuwaj j do przodu, dopóki s[j] jest równe s[i]. Gdy j się zatrzyma — na innej literze lub na końcu — długość ciągu wynosi j-i. Zapisz ją i ustaw i = j. Dla abbbbbbbbbbbb j najpierw zatrzyma się na 1, dając a, a następnie na 13, dając b12.

Ostatni ciąg nie wymaga osobnego przypadku, ponieważ pętla wewnętrzna zatrzymuje się na końcu ciągu znaków. j przesuwa się tylko do przodu, więc czas działania wynosi O(n), a oprócz wyniku przechowujesz dwa indeksy. Wersje w R i Swift najpierw dzielą s na tablicę znaków, więc używają dodatkowej pamięci O(n).

Algorytm

Ustaw i = 0.
Gdy i znajduje się wewnątrz ciągu znaków, ustaw j = i i przesuwaj j do przodu, dopóki znajduje się wewnątrz ciągu znaków i s[j] jest równe s[i].
Zapisz s[i]; jeśli j-i jest większe niż 1, zapisz tę wartość w postaci liczby dziesiętnej.
Ustaw i = j i powtórz.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

Pułapki i przypadki brzegowe

Zapisywanie serii tylko wtedy, gdy napotkasz inną literę. Po ostatnim ccc w aabccc nic już nie następuje, więc zwracasz a2b.
Zapisywanie liczby jako jednego znaku, na przykład '0' + count. To przestaje działać przy 10: dwanaście b wymaga dwóch znaków 12.
Zapisywanie 1 po pojedynczej literze. b pozostaje b, a nie b1.
Ignorowanie wielkości liter. zzZZZ to z2Z3, a nie z5.
Rozbudowywanie niemodyfikowalnego ciągu znaków za pomocą +, jak w Javie lub C#. Każde + kopiuje dotychczasowy wynik, co sprawia, że pętla ma złożoność O(n²); użyj konstruktora ciągu znaków.

Najczęstsze pytania3

Jaka jest złożoność czasowa kompresji ciągów znaków?

Przejście z użyciem dwóch wskaźników zajmuje O(n) czasu, ponieważ indeks skanowania przesuwa się tylko do przodu. Oprócz wyniku przechowuje dwa indeksy, więc dodatkowe zużycie pamięci wynosi O(1).

Czy skompresowany ciąg znaków może być dłuższy niż oryginalny?

Nie w tej wersji. Pojedyncza litera pozostaje jednym znakiem, a ciąg k ≥ 2 liter zamienia się w jedną literę i cyfry liczby k, nigdy nie przekraczając k znaków. Schemat, który zapisuje liczbę po każdej literze, taki jak a1b1, może podwoić długość.

Jak skompresować ciąg znaków w miejscu?

Użyj tablicy znaków z indeksem odczytu i indeksem zapisu. Przeskanuj każdy ciąg znaków indeksem odczytu, a następnie zapisz jego literę i cyfry oznaczające jego długość pod indeksem zapisu. Wynik nigdy nie jest dłuższy niż dotychczas odczytane dane wejściowe, więc indeks zapisu nigdy nie wyprzedza indeksu odczytu. Na końcu zwróć nową długość.