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 fazladan O(1) bellek kullanır. Döngü en fazla m adımdan sonra durur. Önek tablosu O(n × m) zaman alır.

Q: Is Subsequence, en uzun ortak alt diziyle nasıl ilişkilidir?

s , ancak en uzun ortak alt dizilerinin uzunluğu n , yani s 'nin tamamı olduğunda t 'nin bir alt dizisidir. İlk yaklaşımın önek tablosu, bu problem için oluşturduğunuz tablodur. Burada yalnızca s 'nin tamamının sığıp sığmadığını bilmeniz gerekir; bu nedenle açgözlü geçiş yeterlidir.

Kolayİki işaretçi

+10

Sana s ve t adında iki dize verilir. t dizgesinden bazı harfleri (hiç harf silmemek de mümkündür) silerek, kalan harflerin sırasını koruyup s dizgesini elde edebiliyorsan true, aksi takdirde false döndür. Örneğin, ace, abcde dizgesinin bir alt dizisidir, ancak aec değildir.

Fonksiyon

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

sstring: aranacak dize
tstring: harflerin silineceği dizge
Döndürürboolean: true, s dizisi t içinde aralarda boşluklar olabilecek şekilde 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 silin; geriye aynı sırayla ace kalır.

Girdi: s = "aec"t = "abcde"
Çıktı: false
Açıklama: t üç harfin tamamını içerir, ancak tek c, tek e'den önce gelir. 4. indeksteki e'yi kullandıktan sonra sağında hiç c kalmaz.

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

Ek soru

t sabit kalıyorsa ve ona karşı bir milyon s dizgesini kontrol ediyorsan, her kontrolün t'nin tamamını okumaktan daha hızlı olması 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 da s için birçok yerleşim denemeyi düşündürür. Buna gerek yok: s içindeki her harfi yerleşebileceği en erken yerde eşleştirmek, başka herhangi bir seçimden asla daha kötü değildir; dolayısıyla iki işaretçiyle soldan sağa tek bir geçiş yeterlidir.

Önekler üzerinde dinamik programlama

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

Sezgi

dp[i][j], s dizgesinin ilk i harfinin t dizgesinin ilk j harfinin içine sığıp sığmadığını belirtir. t[j-1] olmadan zaten sığıyorsa ya da s[i-1], t[j-1] değerine eşitse ve ilk i-1 harf t[:j-1] içine sığıyorsa sığar. Boş önek her yere sığar ve i. satır yalnızca i-1. satırı okuduğundan, uzunluğu m+1 olan iki satır yeterlidir.

Tablo her hücreyi doldurur: 25.000 harfli s ve 50.000 harfli t için bu, 1.25 × 10^9 hücre demektir.

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, cur[j] değerini cur[j-1] olarak ayarla veya s[i-1], t[j-1]'ye eşitse prev[j-1] olarak ayarla.
prev değerini cur ile değiştir.
prev[m] değerini 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]

İki işaretçiyle açgözlü eşleştirme

Sezgi

İhtiyacın olan bir sonraki s harfini gösteren bir i işaretçisi tut ve t içinde karşılaştığın ilk kopyasını al. Bu seçim güvenlidir. Geçerli bir yerleştirme s[i] harfinin daha sonraki bir kopyasını kullanıyorsa, en erken kopyayı onunla değiştirmek sırayı korur ve s'nin geri kalanı için t'nin daha büyük bir kısmını bırakır. Dolayısıyla herhangi bir yerleştirme varsa açgözlü yaklaşım onu bulur.

Döngü, t'nin her harfini en fazla bir kez okur ve iki dizin tutar: O(n + m) zaman ve O(1) bellek.

Algoritma

s için i = 0 ve t için j = 0 ayarla.
Her iki dizinin indeksleri 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

s içindeki her harfi, önceki eşleşmeden sonra aramak yerine t içinde herhangi bir yerde aramak. Bu, abcde içinde aec dizisinin kabul edilmesine yol açar.
Bir harfin tek bir kopyasını iki kez kullanmak. noon, moon dizisinin bir alt dizisi değildir: 3. indeksteki tek n hem ilk hem de son harf olamaz.
j'nin t'nin sonuna ulaşıp ulaşmadığını döndürmek. s bulunmuş olsun ya da olmasın, döngü çoğu zaman orada sona erer; bunu yalnızca i gösterir.
t tükendiğinde durmamak. ab dizisiyle karşılaştırılan abc, false döndürmelidir.
i, s'nin 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'yi kontrol et.

Sıkça sorulan sorular3

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 fazladan O(1) bellek kullanır. Döngü en fazla m adımdan sonra durur. Önek tablosu O(n × m) zaman alır.

Is Subsequence, en uzun ortak alt diziyle nasıl ilişkilidir?

s, ancak en uzun ortak alt dizilerinin uzunluğu n, yani s'nin tamamı olduğunda t'nin bir alt dizisidir. İlk yaklaşımın önek tablosu, bu problem için oluşturduğunuz tablodur. Burada yalnızca s'nin tamamının sığıp sığmadığını bilmeniz gerekir; bu nedenle açgözlü geçiş yeterlidir.

Bir alt dizi ile bir alt dize 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 bunun tersi geçerli değildir.

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

Test #1

Test #2

Test #3

Argümanlar

s = "ace"
t = "abcde"

Beklenen Çıktı

true