Is Subsequence

Q: Is Subsequence algoritmasının zaman karmaşıklığı nedir?

İki işaretçili çözüm, O(n + m) zamanda çalışır; burada n ve m , s ve t dizelerinin uzunluklarıdır ve O(1) ek bellek kullanır. Uygulamada döngü en fazla m adımdan sonra durur. Önek tablosu O(n × m) zaman alır.

Q: Is Subsequence için açgözlü iki işaretçi yaklaşımı neden işe yarar?

s içindeki bir harfi t içinde mümkün olan en erken yerde eşleştirmek, t 'nin geri kalanını kalan harfler için mümkün olduğunca uzun bırakır. Daha sonraki bir kopyayı kullanan herhangi bir yerleştirme, sıralamayı bozmadan daha erken olanı kullanacak şekilde değiştirilebilir; dolayısıyla herhangi bir yerleştirme varsa, açgözlü yöntem onu bulur.

Q: Aynı t'ye karşı birçok diziyi hızlıca nasıl kontrol edersiniz?

t 'yi bir kez hazırla: her harf için, göründüğü indekslerin sıralı listesini sakla. s[i] 'yi yerleştirmek için, o harfin listesinde önceki eşleşmeden sonraki ilk indeksi ikili aramayla bul. Böylece her kontrol O(m) yerine O(n log m) maliyetine sahip olur.

Kolayİki işaretçi

+10

İki dize alırsın: s ve t. Kalan harfler sıralarını korurken t dizisinden bazı harfleri (hiç harf silmemek de mümkün) silerek onu s dizisine dönüştürebiliyorsan true, aksi hâlde false döndür. Örneğin, ace, abcde dizisinin bir alt dizisidir, ancak aec değildir.

Fonksiyon

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

sstring: aranacak dize
tstring: Harflerin silineceği dize
Döndürürboolean: true, s dizisi t içinde boşluklar bırakılarak da olsa sırayla okunabiliyorsa

Kısıtlar

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s ve t yalnızca küçük İngilizce harfler içerir.

Örnekler

Girdi: s = "ace"t = "abcde"
Çıktı: true
Açıklama: abcde içinden b ve d öğelerini silince, aynı sırayla ace kalır.

Girdi: s = "aec"t = "abcde"
Çıktı: false
Açıklama: t harfinin üçü de var, ancak tek c, tek e'den önce geliyor. 4. indeksteki e'yi kullandıktan sonra sağında hiç c kalmaz.

Girdi: s = "moon"t = "monsoon"
Çıktı: true
Açıklama: monsoon dizgesinin 0 indeksindeki m'yi, 1 ve 4 indekslerindeki o'ları ve 6 indeksindeki n'yi kullan. Aradaki harfler silinir.

Gönderirken +20 gizli test

Ek soru

t aynı kalıyor ve buna karşı bir milyon farklı s dizgesini kontrol etmen gerekiyor diyelim. Her kontrolü t'nin tamamını yeniden okumaktan daha hızlı hâle getirmek için t'yi nasıl hazırlardın?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir alt dizi, t içindeki harfleri herhangi bir yerde atlayabilir; bu yüzden s'yi t içine yerleştirmenin birçok yolunu denemeniz gerekiyormuş gibi görünebilir. Gerek yok. s'nin her harfini yerleştirilebileceği en erken yerde eşleştirmek, başka herhangi bir seçimden asla daha kötü değildir ve böylece arama, iki işaretçiyle soldan sağa tek bir geçişe dönüşür.

Önekler üzerinde dinamik programlama

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

Sezgi

Daha küçük bir soru sor: s dizisinin ilk i harfi, t dizisinin ilk j harfinin içine sığar mı? Yanıta dp[i][j] diyelim. Eğer s dizisinin ilk i harfi t[:j-1] içine sığıyorsa, t[j-1] karakterini silebileceğin için t[:j] içine de sığar. s[i-1], t[j-1] ile eşitse bu harfi de kullanabilirsin; bu durumda s dizisinin ilk i-1 harfi t[:j-1] içine sığmalıdır. Dolayısıyla dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]) olur ve s dizisinin boş öneki her yere sığar.

i. satır yalnızca i-1. satırı okur; bu nedenle m+1 uzunluğunda iki satır yeterlidir. Yanıt, son satırın son hücresidir.

Bu, en uzun ortak alt diziyi bulmak için oluşturduğun tablonun aynısıdır ve doğrudur, ancak her hücreyi doldurur. s dizisi 25,000 harf ve t dizisi 50,000 harf içerdiğinde bu, 1.25 × 10^9 hücre demektir; iki dizinin üzerinden tek bir geçişin gerektirdiğinden çok daha fazlası.

Algoritma

Tüm değerleri true olan, m+1 değerlik bir prev satırı oluştur: boş bir s, t'nin her önekine uyar.
1'den n'ye kadar her i için, cur[0] = false olan bir cur satırı oluştur.
1'den m'ye kadar her j için, s[i-1] ile t[j-1] eşitse cur[j]'yi cur[j-1] ya da prev[j-1] olarak ayarla.
prev'i cur ile değiştir.
prev[m]'yi döndür.

def isSubsequence(s, t):
    n, m = len(s), len(t)
    # prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
    prev = [True] * (m + 1)
    for i in range(1, n + 1):
        cur = [False] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
        prev = cur
    return prev[m]

Greedy eşleştirmeyle iki işaretçi

Sezgi

t dizgesini soldan sağa oku ve hâlâ s dizgesinin sıradaki harfine ihtiyaç duyduğun konumu gösteren i işaretçisini tut. t[j], s[i] ile eşleştiğinde onu kullan ve i değerini ilerlet. Her durumda j değerini ilerlet. i, s dizgesinin sonuna ulaşırsa tüm harfler sırayla bir yer bulmuş demektir.

İlk eşleşmeyi almak neden güvenlidir? Geçerli bir yerleşimin s[i] harfinin daha sonraki bir kopyasını kullandığını varsayalım. Bunu en erken kopyayla değiştirmek sırayı korur ve s dizgesinin geri kalanı için t dizgesinin sağında daha fazla yer bırakır; dolayısıyla açgözlü seçim, var olan bir yerleşimi asla kaybettirmez. moon için monsoon dizgesinde işaretçi 1. indeksteki o harfini alır, n ve s harflerini atlar, 4. indeksteki o harfini alır ve 6. indeksteki n harfinde sona erer.

j, t dizgesindeki her harfi bir kez ziyaret eder ve i yalnızca ileri hareket eder; bu nedenle döngü en fazla m kez çalışır. İhtiyaç duyduğu bellek yalnızca iki indextir.

Algoritma

s için i = 0 ve t için j = 0 ayarla.
Her iki dizin de dizelerinin içindeyken s[i] ile t[j] değerlerini karşılaştır.
Eşitlerse i değerini artır.
Her durumda j değerini artır.
i değerinin s uzunluğuna eşit olup olmadığını döndür.

def isSubsequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

Tuzaklar ve uç durumlar

İki işaretçili döngü kısadır ve hataları uç durumlarda ortaya çıkar.

s içindeki her harfi, önceki eşleşmeden sonra aramak yerine t içinde herhangi bir yerde aramak. Bu, sıralamanın bozulduğu abcde içinde aec dizisini kabul eder.
Bir harfin aynı kopyasını iki kez kullanmak. noon, moon dizisinin bir alt dizisi değildir: moon içinde 3. indekste tek bir n vardır ve bu harf noon dizisinin hem ilk hem de son harfi olamaz.
j değerinin t dizisinin sonuna ulaşıp ulaşmadığını döndürmek. Döngü, s bulunmuş olsun ya da olmasın çoğu zaman orada biter; size yalnızca i bilgi verir.
s dizisinin t dizisinden daha uzun olabileceğini unutmak. ab dizisine karşı abc için false döndürülmelidir; döngü, t tükendiğinde durduğu sürece bunu sağlar.
i, s dizisinin sonuna ulaştıktan sonra s[i] değerini okumak. Python veya Java'da bu okuma hata verir; bu yüzden karşılaştırma yapmadan önce i değerini kontrol edin.

Sıkça sorulan sorular4

Is Subsequence algoritmasının zaman karmaşıklığı nedir?

İki işaretçili çözüm, O(n + m) zamanda çalışır; burada n ve m, s ve t dizelerinin uzunluklarıdır ve O(1) ek bellek kullanır. Uygulamada döngü en fazla m adımdan sonra durur. Önek tablosu O(n × m) zaman alır.

Is Subsequence için açgözlü iki işaretçi yaklaşımı neden işe yarar?

s içindeki bir harfi t içinde mümkün olan en erken yerde eşleştirmek, t'nin geri kalanını kalan harfler için mümkün olduğunca uzun bırakır. Daha sonraki bir kopyayı kullanan herhangi bir yerleştirme, sıralamayı bozmadan daha erken olanı kullanacak şekilde değiştirilebilir; dolayısıyla herhangi bir yerleştirme varsa, açgözlü yöntem onu bulur.

Aynı t'ye karşı birçok diziyi hızlıca nasıl kontrol edersiniz?

t'yi bir kez hazırla: her harf için, göründüğü indekslerin sıralı listesini sakla. s[i]'yi yerleştirmek için, o harfin listesinde önceki eşleşmeden sonraki ilk indeksi ikili aramayla bul. Böylece her kontrol O(m) yerine O(n log m) maliyetine sahip olur.

Bir alt dizi ile bir alt dizge arasındaki fark nedir?

Bir alt dize, art arda gelen harflerden oluşan bir bloktur; alt dizi ise sıra aynı kaldığı sürece harfleri atlayabilir. ace, abcde dizisinin bir alt dizisidir ancak alt dizesi değildir. Her alt dize bir alt dizidir, ancak tersi doğru değildir.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "ace"
t = "abcde"

Beklenen

true