Minimum Window Substring

Q: Minimum Pencere Alt Dizgesinin zaman karmaşıklığı nedir?

Eksik sayaç kullanan kayan pencere, O(n + m) zamanda çalışır; burada n ve m , s ve t dizelerinin uzunluklarıdır. Tablo oluşturulurken t bir kez okunur ve s içindeki her karakter, her hareket için sabit bir maliyetle pencereye en fazla bir kez girip çıkar. Ek bellek, karakter kodu başına bir sayaç içeren bir tablodur ve girdi boyutuyla büyümez.

Q: Sol kenar neden asla geri hareket etmiyor?

Sol kenar, ancak orada başlayan bir pencere t değerini kapsadıktan sonra o konumu geçer ve bu, o başlangıç noktasından itibaren kapsayan en kısa pencereydi. Orada başlayıp daha sonra biten herhangi bir pencere daha uzundur; bu nedenle geri dönmek hiçbir zaman daha iyi bir yanıt bulamaz. Bu yüzden her iki kenar da bir kez ileri doğru ilerler ve işlem doğrusal kalır.

Q: Eksik sayaç neyi sayar?

Pencerenin henüz içermediği ve t ’nin istediği karakter kopyalarının sayısıdır; need içindeki pozitif değerlerin toplamıdır. t uzunluğuyla başlar ve pencere t ’yi kapsadığında tam olarak 0 olur. Fazladan kopyalar bunu hiçbir zaman değiştirmez; böylece her harfi taramak yerine tek bir karşılaştırma yapılabilir.

Q: Minimum Pencere Alt Dizgesi, bir dizgede anagram bulmaktan nasıl farklıdır?

Bir anagram tam olarak t harflerini ve başka hiçbir harfi içermez; bu nedenle pencerenin uzunluğu m olarak sabittir ve her seferinde bir adım kayar. Burada pencere fazladan karakterler içerebilir, dolayısıyla uzunluğu da cevabın bir parçasıdır: t dizisini kapsayana kadar sağdan büyür ve hâlâ kapsadığı sürece soldan küçülür.

ZorKayan pencere Hashing

+10

İki dizge alırsın: s ve t. s içindeki, t’deki her karakteri tekrarları sayarak içeren en kısa alt dizgeyi, yani art arda gelen karakterlerden oluşan bir diziyi bul: t bir harfi iki kez içeriyorsa alt dizge de bu harfi en az iki kez içermelidir. Sıralama önemli değildir ve alt dizge başka karakterler de içerebilir.

Birkaç alt dizgenin uzunluğu aynı ve en kısaysa, en soldakini döndür. s içindeki hiçbir alt dizge t’deki tüm karakterleri içermiyorsa boş bir dizge döndür.

Fonksiyon

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

sstring: içinde arama yapılacak dizge
tstring: pencerenin tekrarlar da dahil olmak üzere içermesi gereken karakterler
Döndürürstring: t'nin tüm karakterlerini içeren, s'nin en kısa ve ardından en soldaki alt dizgesi veya 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.
Birkaç alt dizge en kısaysa, yanıt soldaki olur; hiçbiri yoksa "" olur.

Örnekler

Girdi: s = "mappingtheplan"t = "nap"
Çıktı: "plan"
Açıklama: Soldan okununca, n, a ve p içeren ilk pencere, beş karakter uzunluğundaki appin dizisidir. Sondaki plan, üçünü de 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 tane a ve bir tane n ister. 1. indeksteki ana tam olarak bunu içerir. İkinci bir ana 3. indekste başlar ve en soldaki kazanır.

Girdi: s = "Coddy"t = "cd"
Çıktı: ""
Açıklama: Coddy içindeki tek C büyük harftir ve büyük ve küçük harfler farklı karakterlerdir. Hiçbir alt dize küçük harfli bir c içermez, bu yüzden yanıt boş dizedir.

Gönderirken +17 gizli test

Ek soru

t yalnızca birkaç harf kullanırken ve s uzun olduğunda, s'nin büyük bir 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

Yanıt, bir pencerenin her karakterden kaç tane içerdiğine bağlıdır; karakterlerin sırasına değil ve en iyi pencere herhangi bir yerde başlayabilir. Her başlangıcı her bitişle denemek O(n²) pencere demektir. Sorunu çözen şey, kenarları yalnızca ileri hareket eden bir penceredir: sağ kenar t'yi kapsayana kadar pencereyi genişletir, sol kenar hâlâ kapsıyorken pencereyi daraltır ve eksik karakterleri sayan tek bir sayaç, t'nin kapsanıp kapsanmadığını tek adımda anlamanızı sağlar.

Her başlangıç noktasından bir pencere genişlet

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

Sezgi

Alt dizenin başladığı yeri sabitleyin. Ardından, içindeki her karakterin sayısını tutarak pencereyi her seferinde bir karakter büyütün ve her adımdan sonra t dizgesini kapsayıp kapsamadığını kontrol edin: t dizgesinin kullandığı u farklı harfin her biri için pencerede, t dizgesindeki kadar kopya bulunmalıdır. Koşulu sağlayan ilk bitiş noktası, bu başlangıç için en kısa kapsayan pencereyi verir; çünkü aynı başlangıçtan itibaren daha kısa olanların her biri önce kontrol edilmiş ve başarısız olmuştur. Orada durun.

Bunu her başlangıç için yapın ve en kısa pencereyi saklayın. Başlangıç noktaları soldan sağa denenir ve bir pencere, yalnızca kesin olarak daha kısaysa en iyi pencerenin yerini alır; böylece eşit uzunluktaki pencereler arasında en soldaki kalır.

Pencereler uzun olduğunda veya bulunamadığında bu yöntem yavaştır. s içindeki tek Z en sondaysa ve t bir tane istiyorsa her başlangıç noktası dizgenin sonuna kadar okur: yaklaşık n²/2 adım; bu, n = 5 × 10^4 için 1.25 × 10^9 adımdır ve her adımda en fazla 52 harf kontrol edilir. Hiç pencere bulunmadığında da aynı şey olur.

Algoritma

t içindeki her karakterden kaç kopya istendiğini say ve kullanılan harfleri listele.
Her start için bir sayım tablosunu temizle ve end değerini start konumundan s dizgesinin sonuna kadar ilerletirken s[end] değerini tabloya ekle.
Her eklemeden sonra t içindeki her harfi kontrol et. Pencere her harften yeterince içeriyorsa uzunluğunu şimdiye kadarki en iyi uzunlukla karşılaştır, kesin olarak daha kısaysa onu sakla ve pencereyi büyütmeyi bırak.
Tüm başlangıç konumları denendikten sonra en iyi pencereyi döndür; t içindeki tüm harfleri kapsamıyorsa "" 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 kontrol eden kayan pencere

Sezgi

İki olgu, baştan başlamayı gereksiz kılar. t karakterlerini kapsayan bir pencereye karakter eklemek, pencerenin bu karakterleri kapsamaya devam etmesini sağlar; bir şeyi kapsamayan pencereden karakter çıkarmak ise pencerenin onu kapsamamaya devam etmesini sağlar. Bu nedenle başlangıç sağa kaydıkça, en kısa kapsayan pencerenin bitişi ya yerinde kalabilir ya da sağa kayabilir. Her iki kenar da birlikte ileri doğru ilerleyebilir ve hiçbiri geriye gitmez.

right değerini s üzerinde ilerletip her karakteri sayaç tablosuna ekle. Pencere t karakterlerini kapsadığı her durumda, bu bir adaydır: mevcut en iyiden kısaysa pencereyi kaydet, ardından s[left] karakterini çıkarıp left değerini ilerlet ve yeniden kontrol et. Pencere t karakterlerini kapsamayı bırakana kadar bunu tekrarla, sonra sağdan büyütmeye devam et.

Hiçbir pencere atlanmaz. L ile R arasındaki en iyi pencereyi ele alalım. right, R'ye ulaşmadan önce left, L'yi geçmiş olsaydı, L'den başlayıp R'den önce biten bir pencere t karakterlerini kapsardı ve en iyi pencereden daha kısa olurdu. Dolayısıyla right, R'ye ulaştığında küçültme döngüsü left değerini L'ye kadar ilerletir ve en iyi pencereyi kaydeder. Her kenar en fazla n kez hareket eder; ancak her kontrolde, son kontrolden bu yana yalnızca bir sayaç değişmiş olsa da, t'nin kullandığı her harf için bir tane olmak üzere en fazla u sayaç okunur.

Algoritma

t'nin istediği kopyaların sayısını hesapla ve harflerini listele; boş bir pencereyle, left = 0 ve en iyi uzunluğu n+1 olarak başla.
right'ı her indeks üzerinde ilerlet ve s[right]'ı pencerenin sayaçlarına ekle.
t'deki her harften pencerede yeterli sayıda kopya bulunduğu sürece, pencere en iyi pencereden kesin olarak daha kısaysa onu kaydet, s[left]'i sayaçlardan çıkar ve left'i ilerlet.
En iyi pencereyi döndür veya en iyi uzunluk hâlâ n+1 ise "" 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]
    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 sayaçlı kayan pencere

Sezgi

Aynı pencereyi koruyun ve denetimi tek bir sayıyla değiştirin. need[c], t'nin istediği c kopya sayısından penceredeki kopya sayısı çıkarıldığında kalan değer olsun. Pozitif bir değer, pencerede hâlâ eksik olduğunu; negatif bir değer ise fazladan kopya bulunduğunu gösterir. missing, pencerede eksik olan toplam kopya sayısı olsun; bu değer başlangıçta t'nin uzunluğudur. missing 0 olduğunda pencere t'yi tam olarak kapsar.

Güncelleme tek bir adım sürer. s[right] pencereye girdiğinde ve onun için need 0'dan büyükse bir eksikliği giderir, dolayısıyla missing bir azalır; her iki durumda da need bir azalır ve fazladan kopya olarak 0'ın altına düşebilir. s[left] pencereden çıktığında need bir artar; şimdi 0'dan büyükse pencere, t'nin ihtiyaç duyduğu bir kopyayı vermiştir, dolayısıyla missing bir artar. Fazladan kopyalar, missing'e dokunmadan gelip gider.

s = banana, t = aan için izleyelim: need başlangıçta a için 2, n için 1; missing ise 3'tür. b gerekli değildir. İlk a, missing'i 2'ye; n, 1'e; ikinci a ise 0'a indirir; böylece bana, t'yi kapsar. Pencereyi daraltmak fazladan b'yi çıkarır ve üç karakterli ana'yı bırakır; bu, yeni en iyi sonuçtur. Bu a'yı çıkarmak missing'i yeniden 1'e çıkarır. Son a kapsama durumunu yeniden sağlar ve nana oluşur; bu da ikinci ana'ya kadar daraltılır. Daha kısa olmadığı için soldaki ana kalır.

s'nin her karakteri pencereye bir kez girer ve en fazla bir kez çıkar; her hareket de sabit miktarda iş gerektirir. need'i oluşturmak için t bir kez okunur. Tüm işlem O(n + m) sürer; ek bellek olarak yalnızca 128 sayaçlı bir tablo kullanılır.

Algoritma

need değişkenini t içindeki karakterlerin sayılarıyla doldurun ve missing değerini t uzunluğuna, left = 0 değerine ve en iyi uzunluğu n+1 değerine ayarlayın.
Her right için: need[s[right]] 0'dan büyükse missing değerini azaltın; ardından need[s[right]] değerini azaltın.
missing 0 olduğu sürece, pencere en iyi pencereden kesin olarak daha kısaysa pencereyi kaydedin. Ardından need[s[left]] değerini artırın; değeri artık 0'dan büyükse missing değerini artırın. left değerini 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[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

Çoğu yanlış yanıt, yanlış şeyi sayar veya pencereyi yanlış anda kaydeder.

Kopyalar yerine harfleri saymak. t = aan iki a gerektirir, bu yüzden ban bunu karşılamaz.
Giren her karakter için missing değerini azaltmak. Üçüncü bir a fazladır; missing değerini azaltırsa pencere hâlâ n karakterini içermediği hâlde sayaç 0'a ulaşır. Yalnızca need 0'dan büyükse azalt.
Çıkan her karakter için missing değerini artırmak. Fazladan bir karakteri çıkarmak, pencerenin t'yi karşılamaya devam etmesini sağlar; yalnızca need 0'dan büyük olursa artır.
Pencereyi daraltma döngüsünden sonra kaydetmek. O zamana kadar pencere artık t'yi karşılamaz. s[left] karakterini çıkarmadan önce, pencereyi döngünün içinde kaydet.
Yeni pencere aynı uzunluktaysa en iyi pencereyi değiştirmek. Bu, en kısa pencereler arasından en sağdakini döndürür; katı bir küçüktür karşılaştırması kullan.
"Bulunamadı" uzunluğu olarak n değerini kullanmak. Yanıt s'nin tamamı olduğunda uzunluğu da n olur. İki durumun farklı olması için n+1 ile başla.
c - 'a' ile indekslenen 26 yuvalı bir tablo kullanmak. Büyük harfler bu aralığın dışında kalır. Her karakter kodu için bir yuva kullan.

Sıkça sorulan sorular4

Minimum Pencere Alt Dizgesinin zaman karmaşıklığı nedir?

Eksik sayaç kullanan kayan pencere, O(n + m) zamanda çalışır; burada n ve m, s ve t dizelerinin uzunluklarıdır. Tablo oluşturulurken t bir kez okunur ve s içindeki her karakter, her hareket için sabit bir maliyetle pencereye en fazla bir kez girip çıkar. Ek bellek, karakter kodu başına bir sayaç içeren bir tablodur ve girdi boyutuyla büyümez.

Sol kenar neden asla geri hareket etmiyor?

Sol kenar, ancak orada başlayan bir pencere t değerini kapsadıktan sonra o konumu geçer ve bu, o başlangıç noktasından itibaren kapsayan en kısa pencereydi. Orada başlayıp daha sonra biten herhangi bir pencere daha uzundur; bu nedenle geri dönmek hiçbir zaman daha iyi bir yanıt bulamaz. Bu yüzden her iki kenar da bir kez ileri doğru ilerler ve işlem doğrusal kalır.

Eksik sayaç neyi sayar?

Pencerenin henüz içermediği ve t’nin istediği karakter kopyalarının sayısıdır; need içindeki pozitif değerlerin toplamıdır. t uzunluğuyla başlar ve pencere t’yi kapsadığında tam olarak 0 olur. Fazladan kopyalar bunu hiçbir zaman değiştirmez; böylece her harfi taramak yerine tek bir karşılaştırma yapılabilir.

Minimum Pencere Alt Dizgesi, bir dizgede anagram bulmaktan nasıl farklıdır?

Bir anagram tam olarak t harflerini ve başka hiçbir harfi içermez; bu nedenle pencerenin uzunluğu m olarak sabittir ve her seferinde bir adım kayar. Burada pencere fazladan karakterler içerebilir, dolayısıyla uzunluğu da cevabın bir parçasıdır: t dizisini kapsayana kadar sağdan büyür ve hâlâ kapsadığı sürece soldan küçülür.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "mappingtheplan"
t = "nap"

Beklenen

"plan"

Minimum Window Substring

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her başlangıç noktasından bir pencere genişlet

Her harfi kontrol eden kayan pencere

Eksik sayaçlı kayan pencere

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler