Decode String

Q: Yığın, her parantezden önce gelen metni neden saklar?

Bir [ açıldığında, o düzeyde şimdiye kadar çözümlenmiş metin henüz tamamlanmamıştır: grubun kopyalarının sonuna eklenmesi gerekir. Onu yığına itmek, gövdeyi boş bir dizgeden başlayarak çözerken metni güvende tutar. Eşleşen ] geldiğinde, yığından çıkarmak bu metni geri getirir ve kopyaları metne eklersin.

OrtaYığın Özyineleme

+10

Kodlanmış bir dizede yinelenen metin k[text] biçiminde yazılır; bu, text metninin art arda k kez yazılması anlamına gelir. Gruplar başka grupların içinde yer alabilir; bu nedenle 2[a3[b]], abbbabbb anlamına gelir. Kodlanmış bir s dizesi alan ve çözülmüş dizeyi döndüren bir işlev yaz.

Köşeli parantezlerin dışındaki tüm harfler olduğu gibi kalır. Her sayı, hemen öncesinde bulunduğu [ karakterinden önce yazılmış pozitif bir tam sayıdır ve rakamlar başka hiçbir yerde bulunmaz.

Fonksiyon

decodeString(s: string) → string

sstring: kodlanmış dize
Döndürürstring: çözümlenmiş dize

Kısıtlar

1 ≤ s.length ≤ 10⁴
s yalnızca küçük harfli İngilizce harfler, rakamlar, [ ve ] içerir.
s geçerli bir kodlamadır: her [ işaretinden önce bir sayı bulunur ve eşleşen bir ] işareti vardır; ayrıca hiçbir köşeli parantez boş değildir.
Her k sayısı 1 ≤ k ≤ 300 koşulunu sağlar ve başında sıfır bulunmaz.
Köşeli parantezler en fazla 100 düzey derinliğinde iç içe geçebilir.
Kod çözülmüş dizenin en fazla 5 × 10⁴ karakteri vardır.

Örnekler

Girdi: s = "2[ab]3[c]x"
Çıktı: "ababcccx"
Açıklama: 2[ab], abab sonucunu verir ve 3[c], ccc sonucunu verir. x tüm köşeli parantezlerin dışında yer alır, bu yüzden olduğu gibi kopyalanır ve sonuç ababcccx olur.

Girdi: s = "2[x3[yz]]"
Çıktı: "xyzyzyzxyzyzyz"
Açıklama: Önce iç kısmı çöz: 3[yz], yzyzyz olur; böylece dış grubun gövdesi xyzyzyz olur. İki kez yazıldığında sonuç xyzyzyzxyzyzyz olur.

Girdi: s = "q10[w]e"
Çıktı: "qwwwwwwwwwwe"
Açıklama: Sayı 10, iki basamaktan okunur; bu nedenle q ile e arasında w on kez görünür. Yalnızca [ yanındaki basamağı okuyan kod, bunu 0 kez tekrarlar.

Gönderirken +22 gizli test

Ek soru

Çözümlenmiş dize, girdiden çok daha uzun olabilir. Çözümlenmiş uzunluk 10^18 değerine ulaşabilirken, çözümlenmiş dizgeyi oluşturmadan yalnızca i konumundaki karakteri nasıl döndürürdün?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Sayı köşeli parantezlerden önce gelir, ancak içlerinde ne olduğunu bilmeden kopyaları yazamazsın ve iç kısımda başka gruplar bulunabilir. Bu nedenle bir grup, içindeki tüm gruplar tamamlanmadan genişletilemez. Aşağıdaki yaklaşımların her biri, en içteki grupları önce tamamlamanın bir yoludur: dizgeyi içten dışa yeniden yazmak, özyinelemeli bir çağrının dış gruptan önce iç grubu tamamlamasına izin vermek veya tamamlanmamış dış grupları bir yığında tutmak. Aşağıda n girdinin uzunluğu, m çözümlenmiş dizgenin uzunluğu ve d en derin iç içe geçme düzeyidir.

En içteki grubu genişlet, ardından tekrarla

Sezgi

Dizgeyi kâğıt üzerinde yapacağın gibi çöz. İçinde başka grup olmayan bir grup bul, kopyalarını olduğu yere yaz ve yeniden bak. 2[x3[yz]] içinde 3[yz] grubunun içinde başka bir şey yoktur, bu yüzden dizge 2[xyzyzyz] hâline gelir ve bir kez daha genişletmek yanıtı verir.

Dizgedeki ilk ] her zaman böyle bir grubu kapatır. Ondan önce başka hiçbir grup kapanmamıştır, dolayısıyla onunla [ arasındaki hiçbir şey köşeli ayraç olamaz. Soldaki en yakın [ odur ve sayı, hemen öncesindeki rakam dizisidir. Sayıyı, köşeli ayraçları ve içeriği; içeriği k kez yazarak değiştir ve geriye ] kalmayana kadar tekrarla.

Bu yöntem doğrudur, ancak her genişletme dizgenin tamamını yeniden oluşturur. b grup ve m karaktere doğru büyüyen bir dizge için bu, b × m karakter kopyalamaya kadar çıkar. Yan yana duran yaklaşık 1.300 grup içeren gizli test, 27.688 karakter üretmek için yaklaşık 25 milyon kopyalamaya mal olur; oysa girdinin üzerinde tek bir geçiş yeterli olurdu.

Algoritma

Dizgedeki ilk ] karakterini bul. Yoksa dize çözülmüştür: onu döndür.
Buradan sola doğru en yakın [ karakterine kadar ilerle. Aralarındaki metin grubun gövdesidir.
Bu [ karakterinden önceki rakamlar boyunca daha da sola ilerle ve bunları k sayısı olarak oku.
İlk rakamdan ] karakterine kadar olan her şeyi, gövdeyi k kez yazarak değiştir.
1. adıma geri dön.

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:]

Özyinelemeli iniş

Sezgi

Biçim özyinelemelidir: kodlanmış bir dize, harflerden ve gruplardan oluşan bir dizidir; bir grubun gövdesi de yine kodlanmış bir dizedir. Bu yüzden, paylaşılan bir konumdan o düzeyin sonundaki ] karakterine veya girdinin sonuna ulaşana kadar okuyan ve okuduğu içeriğin çözülmüş hâlini döndüren tek bir decode işlevi yaz.

decode bir rakamla karşılaştığında sayının tamamını okur, [ karakterini atlar ve gövdeyi çözmek için kendisini çağırır. Bu çağrı, eşleşen ] karakterinde durur; çünkü daha derindeki tüm ] karakterleri zaten daha derin bir çağrı tarafından tüketilmiştir. Çağıran işlev ] karakterini atlar, gövdeyi k kez ekler ve okumaya devam eder. 2[x3[yz]] için dış çağrı 2'yi okur; sonraki çağrı x ve 3'ü okur; üçüncü çağrı yz döndürür; ortadaki çağrı xyzyzyz döndürür ve dış çağrı bunu iki kez yazar.

Her girdi karakteri bir kez okunur. Asıl maliyet kopyalamadır: bir çıktı karakteri, çevresindeki her grup için bir kez kopyalanır; dolayısıyla zaman karmaşıklığı, iç içe geçme derinliği d olmak üzere O(n + m·d) olur. Özyineleme de d çağrı derinliğine ulaşır. 100 düzey sorun değildir; ancak çok derin bir girdi çağrı yığınını taşırabilir: örneğin Python, varsayılan olarak iç içe geçmiş çağrıları 1.000 düzeyde durdurur.

Algoritma

Her çağrı tarafından paylaşılan, ilk karakterden başlayan bir pos konumu tutun.
decode(), pos dizenin içindeyken ve bir ] karakterinde değilken döngüye girer.
Bir harfle karşılaşınca onu ekleyin ve ilerleyin.
Bir rakamla karşılaşınca k sayısının tamamını okuyun, [ karakterini atlayın, gövde için decode() çağrısı yapın, ] karakterini atlayın ve gövdeyi k kez ekleyin.
Oluşturulanı döndürün. İlk çağrı, çözümlenmiş dizeyi döndürür.

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()

Yığınla tek geçiş

Sezgi

Özyineleme, açık her grup için tamamlanmamış bir metin parçasını çağrı çerçevelerinde tutar. Bunun yerine bu parçaları kendi yığınında tutabilir ve dizgeyi tek bir döngüde okuyabilirsin.

Geçerli düzey için iki şeyi izle: şimdiye kadar çözümlenen metin olan current ve okunmakta olan sayı olan count. Bir basamak, count değerini count × 10 + digit olarak genişletir; böylece 10 ve 300 doğru elde edilir. Bir [ bir düzey açar: current ve count değerlerini yığına ekle, sonra ikisini de sıfırla. Bir harf current değerine eklenir. Bir ] düzeyi kapatır: kaydedilen metni ve sayıyı yığından çıkar; current, kaydedilen metnin ardından current değerinin count kopyası gelecek şekilde değişir.

2[x3[yz]] ifadesini adım adım izle. İlk [ noktasında (boş, 2) değerlerini yığına eklersin. x, current değerini x yapar. İkinci [ noktasında (x, 3) değerlerini yığına eklersin ve yz, yeni bir current değerini doldurur. İlk ], (x, 3) değerlerini yığından çıkarır; böylece current değeri xyzyzyz olur. Son ] ise (boş, 2) değerlerini yığından çıkarır ve current değeri xyzyzyzxyzyzyz olur.

Gruplar açıldıkları sıranın tersinde kapandığından, yığının en üstü her zaman ] işaretinin geri döneceği düzeydir. İş miktarı özyinelemeyle aynıdır: O(n + m·d); ancak derin iç içe geçme yalnızca bir listeyi büyütür, çağrı yığınını asla büyütmez.

Algoritma

Boş bir yığın, boş bir current ve count = 0 ile başla.
Bir rakam geldiğinde, count = count × 10 + digit olarak ayarla.
[ geldiğinde, (current, count) çiftini yığına ekle, ardından current değerini boş ve count değerini 0 olarak sıfırla.
Bir harf geldiğinde, onu current değerine ekle.
] geldiğinde, (before, k) çiftini yığından çıkar ve current değerini, ardından k kopyası gelen before olacak şekilde ayarla.
Son karakterden sonra current değerini döndür.

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)

Tuzaklar ve uç durumlar

Yanlış cevapların çoğu, sayıyı okurken ya da kaydedilen metnin nereye ekleneceğini belirlerken yapılan hatalardan kaynaklanır.

Bir basamağı sayının tamamı sanmak. q10[w]e ifadesinde sayı 10'dur. Yalnızca [ karakterinden önceki basamağı alan kod, w karakterini 0 kez tekrarlar.
count değerini yığına ekledikten sonra 0'a sıfırlamayı unutmak. Böylece sonraki grubun basamakları eski sayıya eklenir; bu nedenle 2[a3[b]] içteki sayıyı 23 olarak okur.
Kopyaları kaydedilen metinden önce eklemek. Bir ] karakterinde sonuç, gruptan önceki metnin ardından kopyalar gelir; bu yüzden ab2[c] ifadesinin sonucu ccab değil, abcc olur.
En üst düzeydeki harfleri kaybetmek. 2[ab]3[c]x ifadesindeki x hiçbir köşeli parantezin içinde değildir ve yine de cevaba eklenmelidir.
Uzun ve değiştirilemez bir dizgeye her seferinde tek karakter eklemek. Her ekleme dizgenin tamamını kopyalayabilir; bu da 50,000 karakterlik bir cevabı milyarlarca kopyaya dönüştürür. Parçaları bir listede veya bir dizge oluşturucuda toplayın.

Sıkça sorulan sorular4

Decode String'in zaman karmaşıklığı nedir?

Girdiyi okumak O(n) sürer. Çıktıyı oluştururken her karakter, içinde bulunduğu her grup için bir kez kopyalanır; bu nedenle toplam süre O(n + m·d) olur; burada m çözülen uzunluk, d ise iç içe geçme derinliğidir. Her sayı en az 2 olduğunda her grup, çevresindeki grubun en fazla yarısı uzunluğundadır; bu yüzden kopyalama sayısı 2m'nin altında kalır. Hiçbir yaklaşım O(m)'den daha iyi olamaz, çünkü yanıtın kendisi m karakterden oluşur.

Decode String problemini özyineleme ile mi yoksa yığın kullanarak mı çözmelisiniz?

İkisi de aynı işi yapar. Özyineleme, bir grubun gövdesi zaten kodlanmış bir dizge olduğundan biçimi doğrudan izler ve mülakatta yazması genellikle en hızlı yöntemdir. Yığın sürümü de aynı işi tek bir döngüde yapar ve tamamlanmamış dış düzeyleri bir listede tutar; böylece çok derin iç içe geçme çağrı yığınının taşmasına yol açamaz. Görüşmeci binlerce düzey derinliğinde iç içe geçmiş bir girdi hakkında soru sorarsa, yanıt yığındır.

Birden fazla basamağı olan sayıları nasıl ele alırsın?

Sayıyı okudukça oluşturun: 0'dan başlayın ve her basamak için count = count × 10 + digit işlemini yapın. [ geldiğinde sayı tamamlanmış olur; bu nedenle 300[a] 300 verir. Sayıyı yığına ekler eklemez count değerini 0'a sıfırlayın, yoksa sonraki grubun basamakları bu sayıya eklenir.

Yığın, her parantezden önce gelen metni neden saklar?

Bir [ açıldığında, o düzeyde şimdiye kadar çözümlenmiş metin henüz tamamlanmamıştır: grubun kopyalarının sonuna eklenmesi gerekir. Onu yığına itmek, gövdeyi boş bir dizgeden başlayarak çözerken metni güvende tutar. Eşleşen ] geldiğinde, yığından çıkarmak bu metni geri getirir ve kopyaları metne eklersin.

Python

def decodeString(s):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen

"ababcccx"

Decode String

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

En içteki grubu genişlet, ardından tekrarla

Özyinelemeli iniş

Yığınla tek geçiş

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler