Decode String

+10

String yang dikodekan menuliskan teks berulang sebagai k[text]: text ditulis sebanyak k kali berturut-turut. Grup dapat bersarang, jadi 2[a3[b]] mewakili abbbabbb. Diberikan string yang dikodekan s, kembalikan string yang sudah didekode.

Huruf di luar semua tanda kurung tetap seperti semula. Setiap hitungan adalah bilangan bulat positif yang ditulis tepat sebelum [, dan angka tidak muncul di tempat lain.

Fungsi

decodeString(s: string) → string

sstring: string yang dikodekan
Mengembalikanstring: string hasil dekode

Batasan

1 ≤ s.length ≤ 10⁴
s hanya berisi huruf bahasa Inggris kecil, angka, [ dan ].
s adalah pengodean yang valid: setiap [ mengikuti sebuah hitungan dan memiliki ] yang cocok, serta tidak ada tanda kurung siku yang kosong.
Setiap count k memenuhi 1 ≤ k ≤ 300 dan tidak memiliki nol di depan.
Tanda kurung bersarang hingga kedalaman maksimal 100 tingkat.
String yang telah didekode memiliki paling banyak 5 × 10⁴ karakter.

Contoh

Input: s = "2[ab]3[c]x"
Output: "ababcccx"
Penjelasan: 2[ab] menghasilkan abab dan 3[c] menghasilkan ccc. x berada di luar setiap tanda kurung dan disalin apa adanya: ababcccx.

Input: s = "2[x3[yz]]"
Output: "xyzyzyzxyzyzyz"
Penjelasan: Uraikan bagian dalam terlebih dahulu: 3[yz] adalah yzyzyz, jadi bagian luar adalah xyzyzyz. Jika ditulis dua kali, hasilnya adalah xyzyzyzxyzyzyz.

Input: s = "q10[w]e"
Output: "qwwwwwwwwwwe"
Penjelasan: Jumlahnya adalah 10, dibaca dari dua digit, jadi w muncul sepuluh kali di antara q dan e.

Pertanyaan lanjutan

string hasil dekode bisa jauh lebih panjang daripada input. Bagaimana kamu akan mengembalikan karakter pada posisi i tanpa membangun string tersebut, saat panjangnya bisa mencapai 10^18?

Petunjuk

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

0 dari 3 dibuka

Solusi

Kamu tidak bisa menulis salinan suatu grup sebelum mengetahui isinya, dan isinya bisa memuat grup lain. Jadi, setiap pendekatan menyelesaikan grup terdalam terlebih dahulu: tulis ulang string dari dalam ke luar, rekursi ke setiap isi, atau simpan grup terluar yang belum selesai di dalam stack. Di sini, n adalah panjang input, m adalah panjang hasil dekode, dan d adalah kedalaman bersarang.

Perluas grup paling dalam, lalu ulangi

Intuisi

Temukan kelompok yang tidak berisi kelompok lain, tulis salinannya di tempat, lalu cari lagi. ] pertama selalu menutup kelompok seperti itu: belum ada kelompok yang ditutup sebelumnya, jadi isinya tidak memiliki tanda kurung. [ pasangannya adalah tanda kurung terdekat di sebelah kirinya, dan jumlah pengulangannya adalah rangkaian digit sebelumnya. Dalam 2[x3[yz]], 3[yz] dikembangkan terlebih dahulu, sehingga menghasilkan 2[xyzyzyz], lalu satu kali pengembangan lagi memberikan jawabannya.

Setiap pengembangan membangun ulang seluruh string. Dengan b kelompok dan output sepanjang m karakter, jumlah penyalinannya bisa mencapai b × m: 1,000 kelompok yang didekode menjadi 50,000 karakter berarti hingga 5 × 10^7.

Algoritma

Temukan ] pertama. Jika tidak ada, kembalikan string tersebut.
Telusuri ke kiri hingga menemukan [ terdekat. Teks di antaranya adalah isi.
Baca digit sebelum [ itu sebagai jumlah k.
Ganti semua bagian dari digit pertama hingga ] dengan isi yang ditulis sebanyak k kali, lalu ulangi.

def decodeString(s):
    # Expand one innermost group at a time until no bracket is left.
    while True:
        close = s.find("]")
        if close == -1:
            return s
        # The first ']' closes a group with no group inside it,
        # and the nearest '[' to its left opens that group.
        open_ = s.rfind("[", 0, close)
        start = open_
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_])
        s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]

Penurunan rekursif

Intuisi

String yang dienkode adalah urutan huruf dan kelompok, dan isi suatu kelompok adalah string yang dienkode lagi. Jadi, satu fungsi, decode, membaca dari posisi bersama sampai mencapai ] atau akhir input, lalu memanggil dirinya sendiri untuk setiap isi kelompok. Pemanggilan itu berhenti pada ] yang cocok, karena setiap ] yang lebih dalam telah dikonsumsi oleh pemanggilan yang lebih dalam. Untuk 2[x3[yz]], pemanggilan terdalam mengembalikan yz, pemanggilan tengah mengembalikan xyzyzyz, dan pemanggilan terluar menuliskannya dua kali.

Setiap karakter input dibaca sekali, tetapi karakter output disalin sekali untuk setiap kelompok yang mengelilinginya: waktu O(n + m·d). Rekursi mencapai kedalaman d pemanggilan.

Algoritma

Pertahankan satu posisi pos yang digunakan bersama oleh setiap pemanggilan, dimulai dari 0.
decode() melakukan perulangan selama pos masih berada di dalam string dan tidak berada pada ].
Jika menemukan huruf, tambahkan huruf itu lalu lanjutkan.
Jika menemukan digit, baca seluruh angka k, lewati [, panggil decode() untuk bagian isi, lewati ], lalu tambahkan bagian isi sebanyak k kali.
Kembalikan hasil yang sudah dibentuk. Pemanggilan pertama mengembalikan string yang sudah didekode.

def decodeString(s):
    pos = 0

    def decode():
        # Read from pos up to the ']' that closes this level, or the end.
        nonlocal pos
        parts = []
        while pos < len(s) and s[pos] != "]":
            if s[pos].isdigit():
                times = 0
                while s[pos].isdigit():
                    times = times * 10 + int(s[pos])
                    pos += 1
                pos += 1          # skip '['
                inner = decode()  # the group's body, fully decoded
                pos += 1          # skip ']'
                parts.append(inner * times)
            else:
                parts.append(s[pos])
                pos += 1
        return "".join(parts)

    return decode()

Satu lintasan dengan stack

Intuisi

Rekursi menyimpan satu bagian teks yang belum selesai untuk setiap grup terbuka dalam bingkai pemanggilannya. Simpan bagian-bagian itu di tumpukanmu sendiri, dan proses decoding menjadi satu perulangan. [ menyimpan teks yang sudah di-decode pada tingkat ini, beserta jumlahnya, lalu memulai isi grup dengan teks kosong. ] mengambilnya dari tumpukan dan menambahkan salinannya ke teks yang disimpan. Grup ditutup dalam urutan terbalik dari urutan pembukaannya, jadi bagian teratas tumpukan selalu merupakan tingkat yang dituju oleh ].

Dalam 2[x3[yz]], kamu memasukkan (kosong, 2), lalu (x, 3) ke tumpukan. ] pertama mengambil (x, 3) dari tumpukan dan current menjadi xyzyzyz; ] terakhir mengambil (kosong, 2) dari tumpukan dan menggandakannya. Beban kerjanya sebanding dengan rekursi, O(n + m·d), tetapi penyarangan yang dalam menambah ukuran list, bukan tumpukan pemanggilan.

Algoritma

Mulai dengan stack kosong, current kosong, dan count = 0.
Saat menemukan digit, atur count = count × 10 + digit.
Saat menemukan [, masukkan (current, count) ke stack, lalu reset keduanya.
Saat menemukan huruf, tambahkan huruf itu ke current.
Saat menemukan ], keluarkan (before, k) dari stack dan atur current menjadi before yang diikuti k salinan current.
Kembalikan current.

def decodeString(s):
    stack = []      # one entry per open '[': (the text before it, its count)
    current = []    # pieces of the text at the current level
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)   # counts can have several digits
        elif ch == "[":
            stack.append((current, count))
            current, count = [], 0
        elif ch == "]":
            before, times = stack.pop()
            before.append("".join(current) * times)
            current = before
        else:
            current.append(ch)
    return "".join(current)

Jebakan dan kasus tepi

Membaca satu digit sebagai jumlah keseluruhan. Dalam q10[w]e, jumlahnya adalah 10. Jika hanya mengambil digit sebelum [, w diulang 0 kali.
Tidak mengatur ulang count ke 0 setelah memasukkannya. Digit kelompok berikutnya lalu menambahkan angka lama, sehingga 2[a3[b]] membaca jumlah bagian dalamnya sebagai 23.
Meletakkan salinan sebelum teks yang disimpan. ab2[c] adalah abcc, bukan ccab.
Menghilangkan huruf tingkat atas. x dalam 2[ab]3[c]x harus ada dalam jawaban.
Menambahkan satu karakter setiap kali ke string yang tidak dapat diubah. Setiap penambahan dapat menyalin seluruh string, sehingga jawaban sepanjang 50,000 karakter membutuhkan lebih dari satu miliar penyalinan karakter. Kumpulkan potongan dalam list atau string builder.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Decode String?

Membaca input membutuhkan O(n). Setiap karakter output disalin sekali untuk setiap kelompok yang mengelilinginya, sehingga totalnya adalah O(n + m·d), dengan m sebagai panjang hasil dekode dan d sebagai kedalaman penumpukan. Ketika setiap hitungan minimal 2, jumlah penyalinan tetap kurang dari 2m. Tidak ada pendekatan yang lebih baik dari O(m), karena jawaban memiliki m karakter.

Haruskah kamu menyelesaikan Decode String dengan rekursi atau stack?

Keduanya melakukan pekerjaan yang sama. Rekursi mengikuti format secara langsung, karena isi suatu grup adalah string yang dikodekan, dan sering kali paling cepat ditulis. Versi stack berjalan dalam satu perulangan dan menyimpan level yang belum selesai dalam sebuah list, sehingga input yang bertingkat hingga ribuan level tidak dapat membuat call stack meluap.

Bagaimana cara menangani jumlah yang terdiri dari lebih dari satu digit?

Bangun angkanya saat kamu membacanya: mulai dari 0 dan, untuk setiap digit, tetapkan count = count × 10 + digit. Saat [ tiba, angkanya sudah lengkap, jadi 300[a] menghasilkan 300.

def decodeString(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "2[ab]3[c]x"

Output yang diharapkan

"ababcccx"

Decode String

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Perluas grup paling dalam, lalu ulangi

Penurunan rekursif

Satu lintasan dengan stack

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa