Đề bài:
Cho hai chuỗi needle và haystack, trả về chỉ số của lần xuất hiện đầu tiên của needle trong haystack, hoặc -1 nếu needle không là một phần của haystack.
Ví dụ 1:
Input: haystack = "sadbutsad", needle = "sad" Output: 0 Giải thích: "sad" xuất hiện tại vị trí 0 và 6. Lần xuất hiện đầu tiên là tại vị trí 0, vì vậy chúng ta trả về 0.
Ví dụ 2:
Input: haystack = "leetcode", needle = "leeto" Output: -1 Giải thích: "leeto" không xuất hiện trong "leetcode", vì vậy chúng ta trả về -1.
Ràng buộc:
- 1 <= độ dài của haystack, needle <= 10^4
- haystack và needle chỉ chứa các ký tự tiếng Anh viết thường.
Giải thích thuật toán bằng C++
class Solution { public: int strStr(string haystack, string needle) { const int m = haystack.length(); const int n = needle.length(); for (int i = 0; i < m - n + 1; i++) if (haystack.substr(i, n) == needle) return i; return -1; } };
Đây là một phương thức trong lớp `Solution` được sử dụng để tìm kiếm và trả về chỉ số đầu tiên của chuỗi con `needle` trong chuỗi `haystack`. Nếu `needle` không xuất hiện trong `haystack`, phương thức sẽ trả về -1.
Dưới đây là cách thuật toán hoạt động:
1. Khởi tạo hai biến hằng `m` và `n` lần lượt là độ dài của `haystack` và `needle`.
2. Thực hiện vòng lặp `for` từ `i = 0` đến `m – n + 1`. Vòng lặp này sẽ duyệt qua các vị trí trong `haystack` mà có thể chứa được `needle`.
3. Trong mỗi lần lặp, kiểm tra xem chuỗi con của `haystack` bắt đầu từ vị trí `i` và có độ dài `n` có bằng `needle` không bằng cách sử dụng hàm `substr`.
4. Nếu chuỗi con bằng `needle`, trả về giá trị của `i` là chỉ số của lần xuất hiện đầu tiên của `needle` trong `haystack`.
5. Nếu không tìm thấy `needle` trong `haystack` sau khi duyệt qua tất cả các vị trí, trả về -1.
Thuật toán trên hoạt động bằng cách duyệt qua từng vị trí trong `haystack` mà có thể chứa được `needle`, và so sánh chuỗi con tại mỗi vị trí đó với `needle` để xác định xem có khớp hay không. Nếu tìm thấy khớp, trả về chỉ số của lần xuất hiện đầu tiên, nếu không tìm thấy, trả về -1.
Giải thích thuật toán bằng Java
class Solution { public int strStr(String haystack, String needle) { final int m = haystack.length(); final int n = needle.length(); for (int i = 0; i < m - n + 1; ++i) if (haystack.substring(i, i + n).equals(needle)) return i; return -1; } }
Giải thích thuật toán bằng Python
class Solution: def strStr(self, haystack: str, needle: str) -> int: m = len(haystack) n = len(needle) for i in range(m - n + 1): if haystack[i:i + n] == needle: return i return -1
0 / 5 - (0 Đánh Giá)