Bài 28 Leetcode: Find the Index of the First Occurrence in a String

Đề 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á)

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.