Is Subsequence

Q: Berapa kompleksitas waktu Is Subsequence?

Solusi dua pointer berjalan dalam waktu O(n + m) , dengan n dan m sebagai panjang s dan t , serta menggunakan memori tambahan O(1) . Perulangan berhenti setelah paling banyak m langkah. Tabel prefiks membutuhkan waktu O(n × m) .

Q: Apa hubungan Is Subsequence dengan subsekuens umum terpanjang?

s adalah subsekuens dari t tepat ketika subsekuens umum terpanjang mereka memiliki panjang n , yaitu panjang seluruh s . Tabel prefiks dari pendekatan pertama adalah tabel yang kamu buat untuk masalah tersebut. Di sini, kamu hanya perlu mengetahui apakah seluruh s cocok, jadi pemindaian greedy sudah cukup.

MudahTwo pointers

+10

Kamu mendapatkan dua string, s dan t. Kembalikan true jika kamu bisa mengubah t menjadi s dengan menghapus beberapa hurufnya (mungkin tidak ada) sambil mempertahankan urutan huruf yang tersisa, dan false jika tidak. Misalnya, ace adalah subsekuens dari abcde, tetapi aec bukan.

Fungsi

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

sstring: string yang dicari
tstring: string tempat menghapus huruf
Mengembalikanboolean: benar jika s dapat dibaca di dalam t secara berurutan, mungkin dengan jeda

Batasan

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s dan t hanya berisi huruf kecil bahasa Inggris.

Contoh

Input: s = "ace"t = "abcde"
Output: true
Penjelasan: Hapus b dan d dari abcde, maka ace tersisa dengan urutan yang sama.

Input: s = "aec"t = "abcde"
Output: false
Penjelasan: t memiliki ketiga huruf, tetapi satu-satunya c berada sebelum satu-satunya e. Setelah kamu menggunakan e pada indeks 4, tidak ada lagi c di sebelah kanannya.

Input: s = "moon"t = "monsoon"
Output: true
Penjelasan: Gunakan m pada indeks 0, o pada indeks 1 dan 4, serta n pada indeks 6 dari monsoon. Huruf-huruf di antaranya dihapus.

Pertanyaan lanjutan

Jika t tetap dan kamu memeriksa sejuta string s terhadapnya, bagaimana kamu akan menyiapkan t agar setiap pemeriksaan lebih cepat daripada membaca seluruh t?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Subsekuens dapat melewati huruf t di mana saja, sehingga kamu mungkin berpikir untuk mencoba banyak penempatan s. Kamu tidak perlu melakukannya: mencocokkan setiap huruf s di tempat paling awal yang memungkinkan tidak pernah lebih buruk daripada pilihan lain, jadi satu kali penelusuran dari kiri ke kanan dengan dua pointer dapat menentukan hasilnya.

Pemrograman dinamis pada prefiks

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Misalkan dp[i][j] menyatakan apakah i huruf pertama dari s cocok di dalam j huruf pertama dari t. Huruf-huruf tersebut cocok jika sudah cocok tanpa t[j-1], atau jika s[i-1] sama dengan t[j-1] dan i-1 huruf pertama cocok di dalam t[:j-1]. Prefiks kosong cocok di mana saja, dan baris i hanya membaca baris i-1, jadi dua baris dengan panjang m+1 sudah cukup.

Tabel mengisi setiap sel: dengan s yang terdiri dari 25,000 huruf dan t yang terdiri dari 50,000 huruf, jumlahnya 1.25 × 10^9 sel.

Algoritma

Buat baris prev yang terdiri dari m+1 nilai, semuanya true: s yang kosong cocok dengan setiap prefiks t.
Untuk setiap i dari 1 hingga n, buat baris cur dengan cur[0] = false.
Untuk setiap j dari 1 hingga m, tetapkan cur[j] menjadi cur[j-1], atau prev[j-1] jika s[i-1] sama dengan t[j-1].
Ganti prev dengan cur.
Kembalikan prev[m].

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]

Dua pointer dengan pencocokan rakus

Intuisi

Pertahankan pointer i ke huruf berikutnya dari s yang kamu perlukan, lalu ambil kemunculan pertama huruf itu yang kamu temui di t. Pilihan itu aman. Jika penempatan yang valid menggunakan kemunculan s[i] yang lebih akhir, menggantinya dengan kemunculan paling awal akan mempertahankan urutan dan menyisakan lebih banyak bagian t untuk sisa s. Jadi, jika ada penempatan, cara greedy akan menemukannya.

Perulangan membaca setiap huruf t paling banyak satu kali dan menyimpan dua indeks: waktu O(n + m) dan memori O(1).

Algoritma

Atur i = 0 untuk s dan j = 0 untuk t.
Selama kedua indeks berada di dalam string masing-masing, bandingkan s[i] dengan t[j].
Jika keduanya sama, naikkan i.
Naikkan j dalam setiap kasus.
Kembalikan apakah i sama dengan panjang s.

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)

Jebakan dan kasus tepi

Mencari setiap huruf dari s di mana saja dalam t, bukan setelah kecocokan sebelumnya. Cara ini menerima aec dalam abcde.
Menggunakan satu huruf yang sama dua kali. noon bukan subsekuens dari moon: satu-satunya n, pada indeks 3, tidak bisa menjadi huruf pertama sekaligus huruf terakhir.
Mengembalikan apakah j mencapai akhir t. Perulangan sering berakhir di sana, baik s ditemukan maupun tidak; hanya i yang memberi tahu kamu.
Tidak berhenti saat t habis. abc dibandingkan dengan ab harus mengembalikan false.
Membaca s[i] setelah i mencapai akhir s. Dalam Python atau Java, pembacaan itu memunculkan error, jadi periksa i sebelum membandingkan.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Is Subsequence?

Solusi dua pointer berjalan dalam waktu O(n + m), dengan n dan m sebagai panjang s dan t, serta menggunakan memori tambahan O(1). Perulangan berhenti setelah paling banyak m langkah. Tabel prefiks membutuhkan waktu O(n × m).

Apa hubungan Is Subsequence dengan subsekuens umum terpanjang?

s adalah subsekuens dari t tepat ketika subsekuens umum terpanjang mereka memiliki panjang n, yaitu panjang seluruh s. Tabel prefiks dari pendekatan pertama adalah tabel yang kamu buat untuk masalah tersebut. Di sini, kamu hanya perlu mengetahui apakah seluruh s cocok, jadi pemindaian greedy sudah cukup.

Apa perbedaan antara subsekuens dan substring?

Substring adalah rangkaian huruf berurutan, sedangkan subsequence boleh melewati huruf asalkan urutannya tetap sama. ace adalah subsequence dari abcde, tetapi bukan substring darinya. Setiap substring adalah subsequence, tetapi tidak sebaliknya.

def isSubsequence(s, t):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "ace"
t = "abcde"

Output yang diharapkan

true