Is Subsequence

Q: Độ phức tạp thời gian của Is Subsequence là bao nhiêu?

Giải pháp hai con trỏ chạy trong thời gian O(n + m) , trong đó n và m lần lượt là độ dài của s và t , với bộ nhớ bổ sung O(1) . Vòng lặp dừng sau tối đa m bước. Bảng tiền tố cần thời gian O(n × m) .

Q: Is Subsequence liên quan thế nào đến dãy con chung dài nhất (longest common subsequence)?

s là dãy con của t khi và chỉ khi dãy con chung dài nhất của chúng có độ dài n , bằng độ dài của toàn bộ s . Bảng tiền tố của cách tiếp cận đầu tiên là bảng bạn xây dựng cho bài toán đó. Ở đây, bạn chỉ cần biết liệu toàn bộ s có khớp hay không, nên chỉ cần duyệt tham lam.

DễHai con trỏ

+10

Bạn nhận được hai chuỗi, s và t. Trả về true nếu bạn có thể biến t thành s bằng cách xóa một số chữ cái trong đó (có thể không xóa chữ nào) mà vẫn giữ nguyên thứ tự các chữ cái còn lại, và false nếu không thể. Ví dụ, ace là một chuỗi con của abcde, nhưng aec thì không.

Hàm

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

sstring: chuỗi cần tìm
tstring: chuỗi cần xóa chữ cái
Trả vềboolean: true nếu có thể đọc s bên trong t theo đúng thứ tự, có thể có khoảng cách

Ràng buộc

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s và t chỉ chứa các chữ cái tiếng Anh viết thường.

Ví dụ

Đầu vào: s = "ace"t = "abcde"
Đầu ra: true
Giải thích: Xóa b và d khỏi abcde, còn lại ace theo đúng thứ tự.

Đầu vào: s = "aec"t = "abcde"
Đầu ra: false
Giải thích: t có đủ cả ba chữ cái, nhưng c duy nhất nằm trước e duy nhất. Sau khi bạn dùng e ở chỉ số 4, không còn c nào ở bên phải nó.

Đầu vào: s = "moon"t = "monsoon"
Đầu ra: true
Giải thích: Dùng m ở chỉ số 0, các chữ o ở chỉ số 1 và 4, và chữ n ở chỉ số 6 của monsoon. Các chữ cái ở giữa sẽ bị xóa.

Câu hỏi mở rộng

Nếu t không đổi và bạn kiểm tra một triệu chuỗi s với nó, bạn sẽ chuẩn bị t thế nào để mỗi lần kiểm tra nhanh hơn việc đọc toàn bộ t?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Một dãy con có thể bỏ qua các chữ cái ở bất kỳ vị trí nào trong t, nên có vẻ như bạn cần thử nhiều cách đặt s. Nhưng không cần làm vậy: ghép từng chữ cái của s vào vị trí sớm nhất có thể không bao giờ tệ hơn bất kỳ lựa chọn nào khác, nên chỉ cần duyệt từ trái sang phải một lần với hai con trỏ là đủ để xác định.

Lập trình động trên các tiền tố

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Gọi dp[i][j] cho biết i chữ cái đầu tiên của s có nằm trong j chữ cái đầu tiên của t hay không. Chúng nằm trong đó nếu đã nằm trong đó mà không cần t[j-1], hoặc nếu s[i-1] bằng t[j-1] và i-1 chữ cái đầu tiên nằm trong t[:j-1]. Tiền tố rỗng luôn nằm trong mọi vị trí, và hàng i chỉ đọc hàng i-1, nên chỉ cần hai hàng có độ dài m+1.

Bảng điền mọi ô: với s có 25,000 chữ cái và t có 50,000 chữ cái, tổng cộng là 1.25 × 10^9 ô.

Thuật toán

Tạo một hàng prev gồm m+1 giá trị, tất cả đều là true: chuỗi s rỗng khớp với mọi tiền tố của t.
Với mỗi i từ 1 đến n, tạo một hàng cur với cur[0] = false.
Với mỗi j từ 1 đến m, đặt cur[j] bằng cur[j-1], hoặc bằng prev[j-1] khi s[i-1] bằng t[j-1].
Thay prev bằng cur.
Trả về 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]

Hai con trỏ với cách ghép tham lam

Ý tưởng

Giữ một con trỏ i trỏ đến chữ cái tiếp theo của s mà bạn cần, rồi lấy bản sao đầu tiên của chữ đó mà bạn gặp trong t. Cách chọn đó luôn an toàn. Nếu một cách đặt hợp lệ dùng bản sao xuất hiện sau của s[i], việc thay bằng bản sao sớm nhất vẫn giữ nguyên thứ tự và để lại nhiều phần hơn của t cho phần còn lại của s. Vì vậy, nếu tồn tại cách đặt nào, cách chọn tham lam sẽ tìm được.

Vòng lặp đọc mỗi chữ cái của t nhiều nhất một lần và giữ hai chỉ số: thời gian O(n + m) và bộ nhớ O(1).

Thuật toán

Đặt i = 0 cho s và j = 0 cho t.
Khi cả hai chỉ số đều nằm trong chuỗi, hãy so sánh s[i] với t[j].
Nếu chúng bằng nhau, tăng i.
Trong mọi trường hợp, tăng j.
Trả về kết quả cho biết i có bằng độ dài của s hay không.

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)

Lỗi thường gặp và trường hợp biên

Tìm từng chữ cái của s ở bất kỳ vị trí nào trong t, thay vì tìm sau lần khớp trước đó. Cách này chấp nhận aec trong abcde.
Dùng một chữ cái hai lần. noon không phải là chuỗi con của moon: chữ n duy nhất ở chỉ số 3 không thể vừa là chữ cái đầu tiên vừa là chữ cái cuối cùng.
Trả về việc j đã đến cuối t hay chưa. Vòng lặp thường kết thúc ở đó dù có tìm thấy s hay không; chỉ i mới cho bạn biết.
Không dừng lại khi t hết. Với abc và ab, phải trả về false.
Đọc s[i] sau khi i đã đến cuối s. Trong Python hoặc Java, thao tác đọc đó sẽ gây ra lỗi, vì vậy hãy kiểm tra i trước khi so sánh.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Is Subsequence là bao nhiêu?

Giải pháp hai con trỏ chạy trong thời gian O(n + m), trong đó n và m lần lượt là độ dài của s và t, với bộ nhớ bổ sung O(1). Vòng lặp dừng sau tối đa m bước. Bảng tiền tố cần thời gian O(n × m).

Is Subsequence liên quan thế nào đến dãy con chung dài nhất (longest common subsequence)?

s là dãy con của t khi và chỉ khi dãy con chung dài nhất của chúng có độ dài n, bằng độ dài của toàn bộ s. Bảng tiền tố của cách tiếp cận đầu tiên là bảng bạn xây dựng cho bài toán đó. Ở đây, bạn chỉ cần biết liệu toàn bộ s có khớp hay không, nên chỉ cần duyệt tham lam.

Sự khác nhau giữa dãy con và chuỗi con là gì?

Chuỗi con là một khối gồm các chữ cái liên tiếp, còn dãy con có thể bỏ qua một số chữ cái miễn là thứ tự vẫn giữ nguyên. ace là một dãy con của abcde, nhưng không phải là chuỗi con của nó. Mọi chuỗi con đều là dãy con, nhưng điều ngược lại không đúng.

def isSubsequence(s, t):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "ace"
t = "abcde"

Đầu ra mong đợi

true