String Compression

Q: Berapa kompleksitas waktu untuk Kompresi String?

Penelusuran dua pointer memerlukan waktu O(n) , karena indeks pemindaian hanya bergerak maju. Selain hasilnya, penelusuran ini menyimpan dua indeks, jadi ruang tambahan yang diperlukan adalah O(1) .

MudahTwo pointers Array dan string

+10

Kamu mendapat string s yang terdiri dari huruf-huruf bahasa Inggris. Kompres string tersebut: ganti setiap rangkaian dua huruf sama atau lebih yang berurutan dengan huruf itu diikuti panjang rangkaiannya, dan biarkan huruf yang berdiri sendiri apa adanya. Jadi, aabccc menjadi a2bc3. Kembalikan string yang telah dikompres.

Huruf besar dan huruf kecil dianggap berbeda: aA terdiri dari dua rangkaian dengan panjang 1.

Fungsi

compress(s: string) → string

sstring: string yang akan dikompresi, hanya huruf bahasa Inggris
Mengembalikanstring: string terkompresi, setiap rangkaian ditulis sebagai hurufnya diikuti panjangnya jika panjangnya lebih dari 1

Batasan

1 ≤ s.length ≤ 2 × 10⁴
s hanya berisi huruf bahasa Inggris, a hingga z dan A hingga Z.
Panjang run ditulis dalam desimal dan dapat terdiri dari beberapa digit.

Contoh

Input: s = "aabccc"
Output: "a2bc3"
Penjelasan: Rangkaian karakternya adalah aa, b, dan ccc. Hasilnya menjadi a2, b (huruf tunggal tidak mendapat hitungan), dan c3.

Input: s = "abbbbbbbbbbbb"
Output: "ab12"
Penjelasan: Satu a, lalu dua belas b. Panjang 12 ditulis sebagai dua karakter 1 dan 2, jadi hasilnya ab12.

Input: s = "zzZZZ"
Output: "z2Z3"
Penjelasan: Huruf kecil z dan huruf besar Z adalah huruf yang berbeda, jadi ini adalah rangkaian dua huruf diikuti rangkaian tiga huruf: z2Z3.

Pertanyaan lanjutan

Tulis proses kebalikannya: dengan string terkompresi seperti ab12, bangun kembali string aslinya. Bagaimana cara membaca jumlah yang terdiri dari beberapa digit?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Temukan posisi awal dan akhir setiap rentetan huruf yang sama, lalu tulis panjangnya sebagai teks. Rentetan yang terdiri dari satu huruf tidak diberi hitungan, dan hitungan bisa terdiri dari beberapa digit. Dua indeks, satu di awal rentetan dan satu lagi yang bergerak hingga akhir rentetan, melakukan ini dalam satu kali lintasan.

Kumpulkan semua prosesnya, lalu tuliskan

Intuisi

Pertama, catat rangkaian sebagai pasangan huruf dan panjang: untuk aabccc, (a, 2), (b, 1), (c, 3). Setiap huruf memperpanjang rangkaian terakhir atau membuka rangkaian baru. Lalu tulis huruf dari setiap rangkaian, diikuti panjangnya jika lebih dari 1.

Kedua proses berjalan dalam O(n). Daftar dapat memuat n rangkaian jika tidak ada dua huruf bertetangga yang sama, sehingga membutuhkan ruang tambahan O(n).

Algoritma

Buat list kosong untuk rangkaian.
Untuk setiap huruf dalam s: jika rangkaian terakhir memiliki huruf yang sama, tambahkan 1 ke panjangnya; jika tidak, tambahkan rangkaian baru dengan panjang 1.
Untuk setiap rangkaian, tulis hurufnya, lalu panjangnya sebagai teks desimal jika panjangnya lebih dari 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)

Dua pointer di setiap rangkaian

Intuisi

Pertahankan i pada huruf pertama rangkaian saat ini dan majukan j selama s[j] sama dengan s[i]. Saat j berhenti, karena menemukan huruf yang berbeda atau mencapai akhir, panjang rangkaian adalah j-i. Tulis hasilnya dan atur i = j. Pada abbbbbbbbbbbb, j pertama kali berhenti di 1, menghasilkan a, lalu berhenti di 13, menghasilkan b12.

Rangkaian terakhir tidak memerlukan kasus khusus karena perulangan bagian dalam berhenti di akhir string. j hanya bergerak maju, jadi kompleksitas waktunya adalah O(n), dan selain hasilnya, kamu hanya menyimpan dua indeks. Versi R dan Swift terlebih dahulu memecah s menjadi array karakter, jadi keduanya menggunakan ruang tambahan O(n).

Algoritma

Tetapkan i = 0.
Selama i berada di dalam string, tetapkan j = i dan gerakkan j maju selama j berada di dalam string dan s[j] sama dengan s[i].
Tulis s[i]; jika j-i lebih dari 1, tulis nilainya sebagai teks desimal.
Tetapkan i = j dan ulangi.

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)

Jebakan dan kasus tepi

Menulis satu rangkaian hanya saat kamu menemukan huruf yang berbeda. Tidak ada karakter setelah ccc terakhir dalam aabccc, jadi kamu mengembalikan a2b.
Menulis jumlah sebagai satu karakter, seperti '0' + count. Cara ini gagal pada 10: dua belas b memerlukan dua karakter, yaitu 12.
Menulis 1 setelah satu huruf saja. b tetap menjadi b, bukan b1.
Mengabaikan perbedaan huruf besar dan kecil. zzZZZ adalah z2Z3, bukan z5.
Menambahkan isi ke string yang tidak dapat diubah dengan +, seperti dalam Java atau C#. Setiap + menyalin hasil sejauh ini, sehingga perulangan memiliki kompleksitas O(n²); gunakan string builder.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk Kompresi String?

Penelusuran dua pointer memerlukan waktu O(n), karena indeks pemindaian hanya bergerak maju. Selain hasilnya, penelusuran ini menyimpan dua indeks, jadi ruang tambahan yang diperlukan adalah O(1).

Apakah string yang dikompresi bisa lebih panjang daripada string aslinya?

Tidak dalam versi ini. Satu huruf saja tetap satu karakter, dan rangkaian k ≥ 2 huruf menjadi satu huruf ditambah digit-digit k, tidak pernah lebih dari k karakter. Skema yang menulis jumlah setelah setiap huruf, seperti a1b1, dapat menggandakan panjangnya.

Bagaimana cara mengompresi string langsung di tempat?

Gunakan array karakter dengan indeks baca dan indeks tulis. Pindai setiap rangkaian karakter menggunakan indeks baca, lalu tulis hurufnya dan digit panjangnya pada indeks tulis. Output tidak pernah lebih panjang daripada input yang telah dibaca, sehingga indeks tulis tidak pernah mendahului indeks baca. Kembalikan panjang baru di akhir.

def compress(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "aabccc"

Output yang diharapkan

"a2bc3"