找出字符串中第一个匹配项的下标

题目描述

给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。

示例

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

我的解题过程

解题思路：滑动窗口

这道题要在一个字符串中找另一个字符串第一次出现的位置，最直观的思路就是逐个位置去匹配。

具体做法：

• 用 left 指针遍历 haystack，从 0 开始
• 每次取从 left 开始、长度为 needle.length 的子串
• 如果这个子串等于 needle，说明找到了，返回 left
• 如果没找到，left++ 继续往后找
• 注意循环的边界条件：left <= haystack.length - needle.length，因为如果剩余长度不够 needle 的长度，就不用再找了

function strStr(haystack: string, needle: string): number {
  let left = 0;

  while (left <= haystack.length - needle.length) {
    let right = left + needle.length;

    if (haystack.substring(left, right) === needle) {
      return left;
    }

    left++;
  }

  return -1;
}

小结

这道题用的是滑动窗口的思想，每次检查一个固定长度的子串是否匹配。

关键点：

• 循环边界要注意，left 最多到 haystack.length - needle.length
• 使用 substring(left, right) 截取子串，注意 right 是不包含的（左闭右开）
• 如果整个循环都没找到，最后返回 -1

时间复杂度：O(n * m)，其中 n 是 haystack 的长度，m 是 needle 的长度。虽然不是最优解（KMP 算法可以做到 O(n + m)），但对于这道题的数据规模来说足够了，代码也更简洁易懂。

进阶：KMP 算法

如果想要更优的时间复杂度，可以使用 KMP 算法。KMP 的核心思想是：当匹配失败时，利用已经匹配过的信息，避免从头开始重新匹配。

KMP 算法分两步：

1. 构建 next 数组：记录模式串中每个位置的”最长相等前后缀”长度
2. 模式匹配：利用 next 数组在匹配失败时快速跳转

function strStr(haystack: string, needle: string): number {
  if (needle.length === 0) return 0;

  // 构建 next 数组（前缀表）
  const next: number[] = getNext(needle);

  let j = 0; // needle 的指针

  for (let i = 0; i < haystack.length; i++) {
    // 当字符不匹配时，j 回退到 next[j-1] 的位置
    while (j > 0 && haystack[i] !== needle[j]) {
      j = next[j - 1];
    }

    // 如果字符匹配，needle 指针后移
    if (haystack[i] === needle[j]) {
      j++;
    }

    // 如果 needle 完全匹配，返回起始位置
    if (j === needle.length) {
      return i - needle.length + 1;
    }
  }

  return -1;
}

// 构建 next 数组（前缀表）
function getNext(needle: string): number[] {
  const next: number[] = [0];
  let j = 0; // 前缀的末尾位置

  for (let i = 1; i < needle.length; i++) {
    // 当字符不匹配时，j 回退
    while (j > 0 && needle[i] !== needle[j]) {
      j = next[j - 1];
    }

    // 如果字符匹配，前缀长度+1
    if (needle[i] === needle[j]) {
      j++;
    }

    next[i] = j;
  }

  return next;
}

KMP 算法说明：

• next 数组：next[i] 表示在 needle[0...i] 这个子串中，最长相等前后缀的长度
• 例如：needle = "ababc"，next = [0, 0, 1, 2, 0]
  • next[2] = 1：因为 "aba" 的最长相等前后缀是 "a"，长度为 1
  • next[3] = 2：因为 "abab" 的最长相等前后缀是 "ab"，长度为 2
• 匹配过程：当 haystack[i] !== needle[j] 时，不是简单地把 j 重置为 0，而是利用 next 数组跳转到 next[j-1]，这样可以跳过一些不必要的比较

时间复杂度：O(n + m)，空间复杂度：O(m)