Isomorphic Strings

Q: İzomorfik dizgeler için neden iki hash eşlemesine ihtiyacınız var?

s 'den t 'ye olan bir eşleme, s 'deki bir karakterin iki farklı şekilde yeniden adlandırılmasını yakalar. ab ve aa örneklerinde olduğu gibi, s 'deki iki karakterin aynı karakter olarak yeniden adlandırılmasını fark edemez. t 'den s 'ye olan eşleme bu durumu yakalar.

KolayHashing

+10

İki dizge, ilk dizgenin karakterlerini yeniden adlandırarak ikinci dizgeyi elde edebiliyorsan izomorfiktir. Bir karakterin her örneği aynı yeni adı alır, iki farklı karakter asla aynı adı almaz ve bir karakter kendi adını koruyabilir. Aynı uzunluktaki s ve t dizgeleri için, izomorfik olduklarında true, olmadıklarında false döndür.

Fonksiyon

isIsomorphic(s: string, t: string) → boolean

sstring: yeniden adlandırılacak dize, harfler ve rakamlar
tstring: ulaşılacak dize, s ile aynı uzunlukta
Döndürürboolean: s karakterlerinin bire bir yeniden adlandırılması t'yi veriyorsa true

Kısıtlar

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s ve t yalnızca İngilizce harfler ve rakamlar içerir. Büyük ve küçük harfler farklı karakterlerdir.

Örnekler

Girdi: s = "noon"t = "deed"
Çıktı: true
Açıklama: n'yi d olarak ve o'yu e olarak yeniden adlandırın. Her konum bu yeniden adlandırmayla uyumludur ve iki harf farklı adlar alır.

Girdi: s = "moon"t = "deed"
Çıktı: false
Açıklama: Soldan sağa, m d olur ve o e olur, ardından n de d olmak zorunda kalır. İki farklı harf aynı adı paylaşamaz, bu yüzden yanıt false olur.

Girdi: s = "r2d2"t = "c3p3"
Çıktı: true
Açıklama: r, c'ye dönüşür; 2, 3'e dönüşür ve d, p'ye dönüşür. Rakamlar da karakterdir ve her iki 2 de 3 olur.

Ek soru

Bir sözcük listesi verildiğinde, her sözcük çiftini karşılaştırmadan birbirine izomorfik olanları gruplandırabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Yeniden adlandırma her iki yönde de çalışmalıdır: s içindeki her karakter t içindeki bir karaktere dönüşür ve t içindeki her karakter s içindeki bir karakterden gelir. Her iki yönü de tek geçişte kontrol etmek için her yön için bir tane olmak üzere iki eşleme kullanılır.

Her konum çiftini karşılaştırın

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Yeniden adlandırma, eşit karakterleri eşit, farklı karakterleri farklı tutar. Bu nedenle i ve j konumlarındaki her çift için s[i] == s[j] ile t[i] == t[j] aynı sonucu vermelidir. Bu koşul aynı zamanda yeterlidir: her çift aynı sonucu veriyorsa, s içindeki her karakteri, bulunduğu konumlardaki t karakterine eşlemek iyi tanımlıdır ve iki karaktere aynı adı vermez. moon ve deed sözcüklerinde, 0 ve 3 konumları s içinde farklı harfler, ancak t içinde iki kez d içerir; bu nedenle sonuç false olur.

Yaklaşık n²/2 çift vardır: döngüyü erken durduran hiçbir çift olmadığında, n = 2 × 10^4 için 2 × 10^8 karşılaştırma yapılır.

Algoritma

Her i indisi üzerinde döngüye gir ve her biri için daha sonraki her j indisi üzerinde döngüye gir.
s[i] değerinin s[j] değerine eşit olup olmadığını ve t[i] değerinin t[j] değerine eşit olup olmadığını belirle.
İki yanıt farklıysa false döndür.
Son çiftten sonra true döndür.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

Her yön için bir harita

Sezgi

Yeniden adlandırmayı okudukça oluştur. sToT, s içindeki her karakterin neye dönüştüğünü kaydeder; tToS ise t içindeki her karakterin nereden geldiğini kaydeder. i konumunda, a = s[i] ve b = t[i] iken ya ikisi de yenidir ve aralarında bağlantı kurarsın ya da zaten birbirlerini gösteriyor olmalıdırlar.

Tek bir eşleme yeterli değildir. Yalnızca sToT kullanıldığında, moon ve deed geçer; çünkü s içindeki hiçbir harf iki farklı şekilde yeniden adlandırılmaz. Hata, m ve n harflerinin ikisinin de d harfine dönüşmesi ve 3. konumda tToS eşlemesinin d harfinin m harfinden geldiğini zaten belirtmesidir.

Her konum birkaç eşleme işlemi gerektirir; bu yüzden zaman karmaşıklığı O(n)'dir. Her karakter kodu 128'in altındadır; bu nedenle her eşleme 128 elemanlı bir dizi olabilir: alan karmaşıklığı O(1). R ve Swift sürümleri önce dizeleri kod dizilerine kopyalar; bu işlem O(n) sürer.

Algoritma

İki boş eşleme oluştur: sToT ve tToS.
Her i indeksi için a = s[i] ve b = t[i] olsun.
a, sToT içinde değilse ve b, tToS içinde değilse, a'yı b'ye ve b'yi a'ya eşle.
Aksi takdirde, sToT[a] b değilse veya tToS[b] a değilse, false döndür.
Son indeksten sonra true döndür.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

Tuzaklar ve uç durumlar

s'den t'ye tek bir eşleme tutmak. moon ve deed çiftlerini kabul eder; ab ve aa çiftlerini de kabul eder.
Her karakterin kaç kez göründüğünü karşılaştırmak. abcabc ve xyzxzy dizilerinin ikisinde de üç karakter ikişer kez kullanılır; ancak ikinci b, ilkinde y'nin bulunduğu yerde z'nin karşısına gelir.
Büyük ve küçük harfleri eşit kabul etmek. aA iki farklı karakter içerir, bu nedenle bb'ye dönüşemez.
Dizi eşlemelerinin boyutunu yalnızca a'dan z'ye kadar ayarlamak. Büyük harfler ve rakamlar bu aralığın dışındadır; tam karakter kodunu, 128 elemanlı bir dizi kullanarak indeksleyin.

Sıkça sorulan sorular4

İzomorfik Dizelerin zaman karmaşıklığı nedir?

İki harita kullanan çözüm her konumu bir kez okur, bu nedenle O(n) zamanda çalışır. Haritalar, olası her karakter için en fazla bir girdi tutar; toplam 62 harf ve rakam olduğundan ek alan O(1)'dir. Her konum çiftini karşılaştırmak O(n²) zaman alır.

İzomorfik dizgeler için neden iki hash eşlemesine ihtiyacınız var?

s'den t'ye olan bir eşleme, s'deki bir karakterin iki farklı şekilde yeniden adlandırılmasını yakalar. ab ve aa örneklerinde olduğu gibi, s'deki iki karakterin aynı karakter olarak yeniden adlandırılmasını fark edemez. t'den s'ye olan eşleme bu durumu yakalar.

İzomorfizm simetrik midir?

Evet. Bire bir yeniden adlandırma geri alınabilir; bu nedenle s, t olarak yeniden adlandırılırsa, tüm adları tersine çevirmek t'yi tekrar s'ye dönüştürür. isIsomorphic(s, t) ve isIsomorphic(t, s) her zaman aynı sonucu verir.

İki dizenin eşbiçimli olup olmadığını başka nasıl kontrol edebilirsiniz?

Her karakteri ilk göründüğü konumla değiştir ve sonuçları karşılaştır. noon ve deed ikisi de 0 1 1 0 olurken, moon 0 1 1 3 olur. Ayrıca O(n) zaman ve iki örüntü için O(n) bellek gerektirir.

def isIsomorphic(s, t):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

s = "noon"
t = "deed"

Beklenen Çıktı

true