392. Is Subsequence
Tags:
Easy
Skills:
Two pointer
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu kiểm tra xem chuỗi s có phải là một subsequence (dãy con) của chuỗi t hay không. Một subsequence là một chuỗi con có thể thu được từ chuỗi gốc bằng cách xóa đi một số (có thể la 0) ký tự mà không làm thay đổi thứ tự ký tự còn lại
Approach
Dùng two pointers
Ta di chuyển cả hai con trỏ từ trái sang phải. Nếu ký tự tại s[i] trùng với t[j], ta tăng i (tìm ký tự tiếp theo của s). Dù trùng hay không, ta luôn tăng j (vì phải duyệt hết t). Nếu duyệt hết s (tức là i đạt tới độ dài của s), nghĩa là mọi ký tự của s đều đã tìm được vị trí phù hợp trong t, trả về true. Nếu duyệt hết t mà vẫn còn ký tự trong s chưa được kiểm tra, trả về false
Time and space complexity
Solution
1function isSubsequence(s: string, t: string): boolean {
2 let i = 0;
3 let j = 0
4 while (i < s.length && j < t.length) {
5 if (s[i] === t[j]) {
6 i++
7 }
8 j++
9 }
10 return i === s.length
11};i là vị trí đang xét trong s, j là vị trí đang xét trong t.i để xét ký tự tiếp theo của s.j để duyệt tiếp trong t.i đã duyệt hết s (i === s.length), trả về true, ngược lại trả về false.