Permutation in String

Q: Dizedeki Permütasyonun zaman karmaşıklığı nedir?

Kayan pencere kullanıldığında süre O(m + n) olur; burada m , s1 uzunluğudur ve n , s2 uzunluğudur. s1 bir kez sayılır, ardından s2 içindeki her harf pencereye bir kez girer ve pencereden bir kez çıkar. Bunun yerine her pencereyi baştan saymak O(n · m) maliyetlidir.

Q: String içinde Permutation, bir string içinde anagram bulmakla aynı şey midir?

Evet. s1 dizisinin bir permütasyonu onun bir anagramıdır; dolayısıyla soru, s2 içinde m uzunluğunda herhangi bir alt dizenin s1 'in anagramı olup olmadığıdır. İki dizenin tamamı arasındaki anagram kontrolü harf sayılarını bir kez karşılaştırır; burada aynı karşılaştırma, s2 boyunca kayan bir pencere üzerinde yapılır.

Q: Sürgülü pencerenin boyutu burada neden sabit?

s1 ’in her permütasyonunda tam olarak m harf bulunur, bu nedenle yalnızca uzunluğu m olan pencereler eşleşebilir. Tekrarsız en uzun alt dize gibi problemlerde pencere büyüyüp küçülür; burada ise her iki kenar birlikte, her seferinde bir adım hareket eder.

OrtaKayan pencere Hashing

+10

Bir dizgenin permütasyonu, aynı harfleri özgün dizgedekiyle aynı sayıda, herhangi bir sırada kullanır: tar, rat ve art birbirlerinin permütasyonlarıdır. Küçük İngilizce harflerden oluşan s1 ve s2 dizgelerini alırsın. s1'in bir permütasyonu s2 içinde bir alt dize (ardışık karakterlerden oluşan bir dizi) olarak görünüyorsa true, aksi hâlde false döndür.

Fonksiyon

checkInclusion(s1: string, s2: string) → boolean

s1string: yeniden düzenlenecek harfler
s2string: içinde arama yapılacak dize
Döndürürboolean: s2'nin bir alt dizgesi s1'in yeniden sıralanmış hâliyse true

Kısıtlar

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 ve s2 yalnızca küçük İngilizce harfler (a ile z arası) içerir.
s1, s2'den daha uzun olabilir.

Örnekler

Girdi: s1 = "tar"s2 = "smartphone"
Çıktı: true
Açıklama: smartphone sözcüğünde 2 ile 4. indeksler arasındaki art alt dizgesi, tar ile aynı harfler olan bir a, bir r ve bir t içerir.

Girdi: s1 = "noon"s2 = "onion"
Çıktı: false
Açıklama: Uzunluğu 4 olan alt dizeler onio ve nion'dur. noon için iki n ve iki o gerekir; her pencerede bunlardan birinin yerine bir i vardır. noon'daki her harf onion'da bulunur, ancak hiçbir pencerede doğru sayıda harf yoktur.

Girdi: s1 = "abcd"s2 = "dcb"
Çıktı: false
Açıklama: abcd harflerinin herhangi bir permütasyonu 4 harften oluşur, dcb ise yalnızca 3 harfe sahiptir; bu yüzden bir permütasyon içeremez.

Gönderirken +17 gizli test

Ek soru

Bir s1 permütasyonunun başladığı s2 içindeki tüm indisleri, yine O(m + n) zamanda döndürebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

s1 dizisinin permütasyonlarını listelemek umutsuz bir iştir: 10 harfin bile 3.628.800 sıralaması vardır. Çözüm, sıralamayı önemsememektir. s2 içindeki bir alt dize, yalnızca s1 ile aynı m uzunluğuna ve her harften aynı sayıda içeriyorsa s1'in bir permütasyonudur. Dolayısıyla her aday, aynı sabit uzunluktaki bir penceredir ve s2 boyunca tek bir pencereyi kaydırarak her adımda bir harfi çıkarıp bir harfi ekleyerek harf sayılarını güncelleyebilirsin.

Sıfırdan her pencereyi say

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

Sezgi

Kelimesi kelimesine yaklaşım, s1 dizisinin her permütasyonunu oluşturup aramak, hemen tıkanır: 20 harfin 2 × 10^18’den fazla sıralanışı vardır. Bunun yerine soruyu tersinden ele al. s2 içindeki bir alt dizi, tam olarak m harf içeriyorsa ve her harfi s1 ile aynı sayıda kullanıyorsa s1 dizisinin bir permütasyonudur. İçindeki harflerin sırası önemli değildir.

Öyleyse s1 dizisindeki harfleri, a için 0 ve z için 25 indekslerinin kullanıldığı 26 sayılık bir tabloda bir kez say. Ardından s2 içindeki uzunluğu m olan her alt diziyi al, harflerini yeni bir tabloda say ve iki tabloyu karşılaştır. smartphone içindeki tar için pencereler sma, mar, art ve bu şekilde devam eder; art eşleşir: bir a, bir r, bir t.

Bu yöntem doğrudur, çünkü her adayı inceler. Yavaştır, çünkü komşu pencereler m-1 harfi paylaşır ve bunların hepsini yeniden sayarsın. m = 15,000 ve n = 50,000 olduğunda, her biri 15.000 harf içeren 35.001 pencere vardır; bu da yaklaşık 5 × 10^8 adımdır.

Algoritma

s1, s2'den uzunsa false döndür.
s1'deki harfleri 26 sıfır içeren need tablosunda say.
0'dan n-m'ye kadar her başlangıç indeksi için, o başlangıçtan itibaren m karakterin harflerini yeni bir tabloda say.
Bu tablo need'e eşitse true döndür.
Son pencereden sonra false döndür.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

Pencereyi kaydırın ve 26 sayımını karşılaştırın

Sezgi

Yan yana olan iki pencere yalnızca iki harf bakımından farklıdır. mar değerinden art değerine geçerken soldaki m çıkar ve sağa t eklenir. Bu yüzden her adımda m harfini yeniden saymak yerine geçerli pencere için bir tablo tutup bunu bir +1 ve bir -1 ile güncelle.

need tablosunu s1 değerinden, window tablosunu ise s2 değerinin ilk m harfinden doldur ve bunları karşılaştır. Ardından m değerinden n-1 değerine kadar her i için s2[i] değerini ekle, s2[i-m] değerini çıkar ve yeniden karşılaştır. Pencere artık s2[i-m+1..i] olur ve hâlâ m harf uzunluğundadır.

Her adım, m ne olursa olsun iki güncelleme ve 26 sayının karşılaştırılması kadar işlem gerektirir. En büyük girdide bu yaklaşık 26 × 50,000 = 1.3 × 10^6 işlem eder ve s2 uzunluğuna göre doğrusaldır. Bu, çoğu mülakatçının beklediği çözümdür.

Algoritma

s1, s2'den daha uzunsa false döndür.
s1'i need içine, s2'nin ilk m harfini window içine say.
İki tablo eşitse true döndür.
m'den n-1'e kadar her i için: s2[i] için 1 ekle, s2[i-m] için 1 çıkar ve tablolar eşitse true döndür.
false döndür.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

Pencereyi kaydırın ve dengelenmemiş harfleri takip edin

Sezgi

Her adımda 26 sayıyı karşılaştırmak işi tekrarlar, çünkü bir adımda yalnızca ikisi değişir. Bunun yerine tek bir balance tablosu tut: balance[c], s1 içindeki c harfinin kopya sayısından penceredeki kopya sayısının çıkarılmasıyla elde edilen değerdir. Pencere, 26 dengenin tümü 0 olduğunda tam olarak s1'in bir permütasyonudur. Tablonun yanında, dengesi 0 olmayan harflerin sayısı olan unbalanced değerini tut ve 0'a ulaştığı anda true yanıtını ver.

Kayıt tutmanın tek bir kuralı var. balance[c] değerini değiştirmeden önce, 0 ise harfin dengesi bozulmak üzeredir; bu yüzden unbalanced değerini 1 artır. Değişiklikten sonra 0 ise harfin dengesi sağlanmıştır; bu yüzden değeri 1 azalt. Pencereye giren bir harfin dengesi 1 azalır; pencereden çıkan bir harfin dengesi 1 artar. Bir dengenin 2'den 1'e geçmesi iki kontrolden hiçbirini tetiklemez; bu doğrudur: harfin dengesi bozuktu ve hâlâ bozuk.

tar ve smartphone dizilerini adım adım inceleyelim. Başlangıçta dengeler a: 1, r: 1, t: 1 olduğundan unbalanced değeri 3'tür. s ve m girerek değeri 5'e çıkarır; ardından a girer ve a'nın değerini 0'a indirir: 4. r girer (3), s çıkarken (2). t girer (1), m çıkarken (0) ve art penceresi yanıttır.

unbalanced == 0 koşulunu ilk harften itibaren test edebilirsin. Pencere m harften daha azını içerirken dengelerin toplamı pozitif bir sayıdır; dolayısıyla en az biri 0 değildir. Her adım sabit miktarda iş yapar; bu yüzden taramanın tamamı O(m + n) sürer ve tabloda her zaman 26 sayı bulunur; bu da O(1) alan demektir.

Algoritma

s1, s2'den uzunsa false döndür.
s1'i balance içinde say ve unbalanced değerini bakiyesi 0 olmayan harflerin sayısına ayarla.
s2'nin her i indeksi için s2[i]'nin bakiyesinden 1 çıkar; bu bakiye 0 ise unbalanced değerine 1 ekle, 0 olursa 1 çıkar.
i ≥ m ise aynı hesaplamayı yaparak s2[i-m]'nin bakiyesine 1 ekle.
unbalanced 0 ise true döndür. Döngüden sonra false döndür.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu pencerenin kenarlarından ya da harflerin kaç kez göründüğünü değil, hangi harflerin göründüğünü kontrol etmekten kaynaklanır.

Yalnızca s1 içindeki her harfin pencerede bulunduğunu kontrol etmek. onio, noon içindeki tüm harfleri içerir; ancak onun bir permütasyonu değildir. Sayıları karşılaştırın.
Yanlış harfi çıkarmak. s2[i] pencereye girdiğinde, çıkan harf s2[i-m] olur; böylece pencere s2[i-m+1..i] hâline gelir. s2[i-m+1] harfini çıkarmak, pencerede m-1 harf bırakır.
İlk pencereyi atlamak. Yalnızca pencereyi kaydırdıktan sonra karşılaştırırsanız, 0 indeksindeki bir permütasyon asla bulunamaz.
s1 uzunluğunun s2 uzunluğundan fazla olduğu durumu unutmak. Rust'ta işaretsiz uzunluklarda n - m taşmaya neden olur; Swift'te ise 0...(n - m) aralığı çöker. Önce false döndürün.
Dizi başvurularını karşılaştıran bir dilde dizileri == ile karşılaştırmak. JavaScript ve Dart'ta iki farklı dizi hiçbir zaman == değildir; Java'da Arrays.equals kullanın.

Sıkça sorulan sorular4

Dizedeki Permütasyonun zaman karmaşıklığı nedir?

Kayan pencere kullanıldığında süre O(m + n) olur; burada m, s1 uzunluğudur ve n, s2 uzunluğudur. s1 bir kez sayılır, ardından s2 içindeki her harf pencereye bir kez girer ve pencereden bir kez çıkar. Bunun yerine her pencereyi baştan saymak O(n · m) maliyetlidir.

String içinde Permutation, bir string içinde anagram bulmakla aynı şey midir?

Evet. s1 dizisinin bir permütasyonu onun bir anagramıdır; dolayısıyla soru, s2 içinde m uzunluğunda herhangi bir alt dizenin s1'in anagramı olup olmadığıdır. İki dizenin tamamı arasındaki anagram kontrolü harf sayılarını bir kez karşılaştırır; burada aynı karşılaştırma, s2 boyunca kayan bir pencere üzerinde yapılır.

Sürgülü pencerenin boyutu burada neden sabit?

s1’in her permütasyonunda tam olarak m harf bulunur, bu nedenle yalnızca uzunluğu m olan pencereler eşleşebilir. Tekrarsız en uzun alt dize gibi problemlerde pencere büyüyüp küçülür; burada ise her iki kenar birlikte, her seferinde bir adım hareket eder.

26 sayaçtan oluşan bir dizi yerine hash map kullanabilir miyim?

Evet, dizeler herhangi bir karakter içerebiliyorsa bir tanesine ihtiyacın var. Yalnızca küçük harfler söz konusuysa 26 elemanlı bir dizi daha hızlıdır ve sabit alan kullanır. Bir map kullanırken, aynı harflere sahip iki map’in eşit sayılması için sayısı 0’a düştüğünde anahtarı sil ya da son yaklaşımdaki unbalanced sayacını kullan; map ile de aynı şekilde çalışır.

Python

def checkInclusion(s1, s2):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s1 = "tar"
s2 = "smartphone"

Beklenen

true

Permutation in String

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Sıfırdan her pencereyi say

Pencereyi kaydırın ve 26 sayımını karşılaştırın

Pencereyi kaydırın ve dengelenmemiş harfleri takip edin

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler