Lời giải đề bài tuần trước:
Với string “s” và một dãy các string “words” đã cho, cho biết có bao nhiêu string trong tập “words” là dãy con của “s”?
Lời giải:
Đây là một bài mở rộng của bài kiểm tra dãy con: Is Subsequence, vì vậy ta có ngay cách tiếp cận là: với mỗi string “word” trong “words”, ta kiểm tra xem “word” có phải là dãy con của “s” hay không? Nếu đúng, ta tăng biến đếm lên 1. Ta có giải mã như sau:
https://pastebin.com/vR2EBpxt
Tuỳ vào cách thực hiện hàm “isSubsequence”, giải thuật sẽ có độ phức tạp khác nhau.
Ví dụ: Bằng cách kiểm tra tuyến tính, ta có độ phức tạp giải thuật time complexity là O(W*S), trong đó:
- W là số string trong “words”,
- S là độ dài string “s”.
Với cách tiếp cận trên, ta phải duyệt string “s” W lần. Áp dụng vào bài này, string “s” dài hơn rất nhiều so với string trong “words”:
Constraints:
- 1 <= s.length <= 5 * 10^4- 1 <= words.length <= 5000
Vì vậy, ta cần một cách tiếp cận khác, tối ưu hơn. Nếu ta có thể chỉ duyệt string “s” một lần, liệu ta có thể có độ phức tạp time complexity tốt hơn so với giải thuật trên không?
Tại mỗi kí tự “sch” của string “s”, ta thử tìm kí tự tương ứng của mỗi string “word” trong tập “words” như sau:
Ví dụ: s = "apppleen", words = ["apple", "pen"]
- Ta nhóm string trong “words” theo kí tự đầu tiên:
heads = { 'a': ["apple"], 'p': ["pen"] }
- Với sch là “a” ([a]pppleen), ta tăng vị trí của các từ trong group ‘a’ lên 1, ta có:
heads = { 'p': ["pple", "pen"] }
- Với sch là “p” (a[p]ppleen), ta tăng vị trí của các từ trong group ‘p’ lên 1, ta có:
heads = { 'p': ["ple"], 'e': ["en"] }
- Tiếp tục duyệt string “s” cho tới cuối cùng, ta sẽ có kết quả của bài toán.
