28. Find the Index of the First Occurrence in a String

Problem

Bài toán yêu cầu tìm chỉ số đầu tiêm mà chuỗi con needle xuất hiện trong chuỗi haystack . Nếu không tồn tại, return -1 . Nếu needle là chuỗi rỗng, return 0

Approach

Duyệt từng vị trí trong haystack từ 0 đến haystack.length - needle.length

Tại mỗi vị trí, so sánh đoạn con của haystack với needle

Nếu trùng khớp, return về chỉ số đó

Nếu duyệt hết mà không tìm thấy, return -1

Time and space complexity

TC: O((n - m) * m), với n là độ dài haystack , m là độ dài needle

SC: O(1)

Solution

typescripttypescript

1function strStr(haystack: string, needle: string): number {
2    if(needle.length === 0) return 0;
3    const n = haystack.length;
4    const m = needle.length;
5    for(let i =0; i <= n - m; i++) {
6	    if(haystack.substring(i, i + m) === needle) {
7		    return i
8	    }
9    }
10    
11    return -1
12};

💡

Giải thích

Nếu needle rỗng, return 0

Duyệt từng chỉ số i từ 0 -> n - m

Tại mỗi vị trí, lấy chuỗi con từ i -> i + m

Nếu trùng, return i

Nếu không tìm thấy, return -1

💡

Một số lưu ý mở rộng

Nếu muốn tối ưu hơn cho trường hợp chuỗi lớn, có thể dùng thuật toán KMP, Rabin-Karp

Approach - Rabin-Karp

💡

Rabin Karp

Là một thuật toán tìm

Loading content...