Minimum Window Substring

Q: Minimum Window Substring’in zaman karmaşıklığı nedir?

Eksik sayaç penceresi, n ve m , sırasıyla s ve t dizelerinin uzunlukları olmak üzere O(n + m) zamanda çalışır. Tablo oluşturulurken t bir kez okunur ve s içindeki her karakter pencereye en fazla bir kez girip çıkar. Ek bellek, karakter kodu başına bir sayaçtır.

Q: Sol kenar neden asla geri hareket etmiyor?

Sol kenar, yalnızca oradan başlayan pencere t değerini kapsadıktan sonra bir konumu geçer ve bu pencere o başlangıç noktasından itibaren kapsayan en kısa pencere olur. Oradan başlayıp daha sonra biten herhangi bir pencere daha uzundur; bu yüzden geriye dönmek hiçbir zaman daha iyi bir yanıt bulamaz.

Q: Minimum Window Substring, bir dizede anagram bulmaktan nasıl farklıdır?

Bir anagram, t içindeki harflerin tam olarak aynısını içerir; bu nedenle penceresinin uzunluğu sabittir: m ve pencere her seferinde bir adım kayar. Burada fazladan karakterlere izin verilir, bu yüzden uzunluk da cevabın bir parçasıdır: pencere t 'yi kapsayana kadar büyür ve hâlâ kapsadığı sürece küçülür.

ZorKayan pencere Hashing

+10

İki dizge alırsın: s ve t. t'deki her karakteri tekrar sayısını da dikkate alarak içeren s'nin en kısa alt dizgesini bul: t bir harfi iki kez içeriyorsa, alt dizge de o harfi en az iki kez içermelidir. Sıralama önemli değildir ve başka karakterler de bulunabilir.

En kısa birkaç alt dizge varsa, en soldakini döndür. t'deki tüm karakterleri içeren bir alt dizge yoksa, boş bir dizge döndür.

Fonksiyon

minWindow(s: string, t: string) → string

sstring: içinde arama yapılacak dize
tstring: pencerenin içermesi gereken karakterler, tekrarlar da dahil
Döndürürstring: s'nin, t'nin tamamını içeren en kısa ve ardından en soldaki alt dizisi ya da boş bir dize

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ t.length ≤ 10⁴
s ve t yalnızca İngilizce harfler içerir. Büyük ve küçük harfler farklı karakterlerdir.
En kısa alt dizelerden birden fazlası varsa, yanıt soldaki olur; hiçbiri yoksa, "" olur.

Örnekler

Girdi: s = "mappingtheplan"t = "nap"
Çıktı: "plan"
Açıklama: Soldan başlayarak n, a ve p harflerini içeren ilk pencere, beş karakterlik appin'dir. plan bu üçünü dört karakterde içerir ve üç karakterlik hiçbir dizi bunların hepsini içermez.

Girdi: s = "banana"t = "aan"
Çıktı: "ana"
Açıklama: t, iki a kopyası ve bir n ister. 1. dizindeki ana tam olarak bunu içerir. İkinci bir ana 3. dizinde başlar ve soldaki kazanır.

Girdi: s = "Coddy"t = "cd"
Çıktı: ""
Açıklama: Coddy'deki C büyük harftir ve c'den farklı bir karakterdir. Hiçbir alt dize küçük harfli c içermez, bu nedenle yanıt boş dizedir.

Ek soru

t az sayıda harften oluşup s uzun olduğunda, s'nin büyük kısmı hiçbir zaman önemli olmaz. Pencerenin yalnızca t'deki bir harfi içeren konumlar arasında atlamasını sağlayabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir penceredeki karakterlerin sırası değil, yalnızca sayıları önemlidir. Pencere t’yi kapsayana kadar sağ kenarı, ardından kapsadığı sürece sol kenarı hareket ettir; hiçbir kenar geri gitmez. Eksik karakterleri sayan bir sayaç, pencerenin t’yi kapsayıp kapsamadığını tek adımda anlamanı sağlar.

Her başlangıçtan bir pencere büyütün

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

Sezgi

Bir başlangıç noktası sabitle ve her seferinde bir karakter ekleyerek pencereyi büyüt; her karakterin sayısını tut. Her adımdan sonra t'nin kullandığı u harfin her birini kontrol et. Koşulu sağlayan ilk bitiş, bu başlangıç noktasından itibaren tüm harfleri kapsayan en kısa pencereyi verir; bu yüzden orada dur. Başlangıç noktaları soldan sağa ilerler ve en iyi pencerenin yerini yalnızca kesin olarak daha kısa bir pencere alır; böylece eşitlik durumlarında soldaki korunur.

Hiç pencere yoksa her başlangıç noktası s'nin sonuna kadar okunur: yaklaşık n²/2 adım, n = 5 × 10^4 için 1.25 × 10^9.

Algoritma

t'nin istediği her harften kaç kopya olduğunu say.
Her start için bir sayım tablosunu temizle ve s[end] ekleyerek end'i sağa ilerlet.
Pencere her harften yeterli sayıda içerdiğinde, en iyisinden kesin olarak daha kısaysa onu sakla ve sonraki başlangıca geç.
En iyi pencereyi döndür veya t'nin kapsamına giren hiçbir pencere yoksa "" döndür.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    best_start, best_len = 0, len(s) + 1
    for start in range(len(s)):
        have = [0] * 128  # counts inside s[start..end]
        for end in range(start, len(s)):
            have[ord(s[end])] += 1
            if all(have[c] >= need[c] for c in letters):
                # The first end that covers t gives the shortest window from this start.
                if end - start + 1 < best_len:
                    best_start, best_len = start, end - start + 1
                break
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Her harfi denetleyen kayan pencere

Sezgi

Örten pencereye karakter eklemek, pencerenin örtmeye devam etmesini sağlar; bir şeyi kaçıran pencereden karakter çıkarmak ise onu kaçırmaya devam ettirir. Bu nedenle başlangıç sağa ilerledikçe en kısa örten pencerenin sonu asla sola ilerlemez.

Hiçbir pencere gözden kaçmaz. L ile R arasındaki en iyi pencereyi ele alalım. right, R'ye ulaşmadan önce left'in L'yi geçmesi için L'den başlayan daha kısa bir pencerenin t'yi kapsaması gerekirdi. Dolayısıyla right, R'ye ulaştığında daraltma işlemi left'i L'ye kadar ilerletir ve pencereyi kaydeder.

Her kenar en fazla n kez hareket eder; ancak her kontrol en fazla u sayısını okur: O(n·u).

Algoritma

t'nin istediği kopyaları sayın; left = 0 olarak ayarlayın ve en iyi uzunluğu n+1 yapın.
Her right için s[right]'ı pencerenin sayılarına ekleyin.
t'deki her harften yeterli sayıda kopya bulunduğu sürece, pencere kesin olarak daha kısaysa onu kaydedin, s[left]'i çıkarın ve left'i ilerletin.
En iyi pencereyi döndürün veya en iyi uzunluk hâlâ n+1 ise "" döndürün.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    have = [0] * 128  # counts inside s[left..right]

    def covers():
        for c in letters:
            if have[c] < need[c]:
                return False
        return True

    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        have[ord(s[right])] += 1  # expand on the right
        while covers():  # shrink from the left while the window still covers t
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            have[ord(s[left])] -= 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Eksik sayacıyla kayan pencere

Sezgi

Taramayı tek bir sayıyla değiştir. need[c], t'nin istediği c karakterinin sayısından penceredeki sayısını çıkardığında elde edilen değeri göstersin; negatif bir değer fazlalık olduğunu belirtir. missing, pencerenin hâlâ eksik olan kopyalarının sayısı olsun; başlangıç değeri t'nin uzunluğudur. missing 0 olduğunda pencere t'yi tam olarak kapsar.

need değeri 0'ın üzerindeyken pencereye giren bir karakter bir boşluğu doldurur, dolayısıyla missing azalır. Çıkarılması need değerini 0'ın üzerine çıkaran bir karakter bir boşluk açar, dolayısıyla missing artar. Fazlalık karakterler bunu etkilemez. t = aan için banana üzerinde missing ilk olarak bana penceresinde 0'a ulaşır ve fazlalık olan b çıkarıldığında ana hâlâ kapsama sağlar.

Her karakter sabit bir maliyetle bir kez girip bir kez çıkar: O(n + m) zaman ve 128 sayaçtan oluşan tek bir tablo.

Algoritma

need değişkenini t karakterlerinin sayılarıyla doldur; missing değerini t uzunluğuna, left = 0 değerine ve en iyi uzunluğu n+1 değerine ayarla.
Her right için: need[s[right]] 0'dan büyükse missing değerini azalt; ardından need[s[right]] değerini azalt.
missing 0 iken, pencere kesin olarak daha kısaysa pencereyi kaydet. need[s[left]] değerini artır; artık 0'dan büyükse missing değerini artır. left değerini ilerlet.
En iyi pencereyi döndür veya en iyi uzunluk hâlâ n+1 ise "" döndür.

def minWindow(s, t):
    # need[c]: copies of c that t asks for minus copies inside the window.
    # Positive means the window still lacks c; negative means it holds spares.
    need = [0] * 128
    for ch in t:
        need[ord(ch)] += 1
    missing = len(t)  # characters of t the window does not cover yet
    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        c = ord(s[right])
        if need[c] > 0:  # this copy fills a gap
            missing -= 1
        need[c] -= 1
        while missing == 0:  # the window covers t: record it, then shrink
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            c = ord(s[left])
            need[c] += 1
            if need[c] > 0:  # gave away a copy t needs
                missing += 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Tuzaklar ve uç durumlar

Kopya sayısı yerine harfleri saymak. t = aan için iki a gerekir, bu yüzden ban bunu karşılamaz.
Her karakter pencereye girdiğinde veya pencereden çıktığında missing değerini değiştirmek. Böylece fazladan bir a hesaba katılır ve pencere n harfini içermediği hâlde missing 0 olabilir.
Eşit uzunluktaki bir pencerede en iyi pencereyi değiştirmek. İkinci örnekte bu, 3. indeksteki ana sonucunu döndürür.
"Bulunamadı" uzunluğu olarak n kullanmak. Yanıt s dizgesinin tamamı olduğunda uzunluğu da n olur; n+1 ile başlayın.
c - 'a' ile indekslenen 26 elemanlı bir tablo kullanmak. Üçüncü örnekte olduğu gibi büyük harfler bu aralığın dışında kalır.

Sıkça sorulan sorular3

Minimum Window Substring’in zaman karmaşıklığı nedir?

Eksik sayaç penceresi, n ve m, sırasıyla s ve t dizelerinin uzunlukları olmak üzere O(n + m) zamanda çalışır. Tablo oluşturulurken t bir kez okunur ve s içindeki her karakter pencereye en fazla bir kez girip çıkar. Ek bellek, karakter kodu başına bir sayaçtır.

Sol kenar neden asla geri hareket etmiyor?

Sol kenar, yalnızca oradan başlayan pencere t değerini kapsadıktan sonra bir konumu geçer ve bu pencere o başlangıç noktasından itibaren kapsayan en kısa pencere olur. Oradan başlayıp daha sonra biten herhangi bir pencere daha uzundur; bu yüzden geriye dönmek hiçbir zaman daha iyi bir yanıt bulamaz.

Minimum Window Substring, bir dizede anagram bulmaktan nasıl farklıdır?

Bir anagram, t içindeki harflerin tam olarak aynısını içerir; bu nedenle penceresinin uzunluğu sabittir: m ve pencere her seferinde bir adım kayar. Burada fazladan karakterlere izin verilir, bu yüzden uzunluk da cevabın bir parçasıdır: pencere t'yi kapsayana kadar büyür ve hâlâ kapsadığı sürece küçülür.

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

Test #1

Test #2

Test #3

Argümanlar

s = "mappingtheplan"
t = "nap"

Beklenen Çıktı

"plan"

Minimum Window Substring

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her başlangıçtan bir pencere büyütün

Her harfi denetleyen kayan pencere

Eksik sayacıyla kayan pencere

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler