找出字符串中第一个匹配项的下标 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

示例 1

输入：haystack = "sadbutsad", needle = "sad"

输出：0

"sad" 在下标 0 和 6 处匹配，第一个匹配项的下标是 0。

示例 2

输入：haystack = "leetcode", needle = "leeto"

输出：-1

"leeto" 没有在 "leetcode" 中出现。

💭 模拟答题者思考

1. 我先想暴力：在 haystack 的每个下标 i 尝试把 needle 对齐上去，逐字符比较——逻辑直接，但最坏要试 O(n) 个起点、每次比 O(m) 个字符。

2. 重复在哪里？每个起点 i 都在做同一件事：检查 haystack[i..i+m-1] 是否等于 needle。一旦某字符不等就可以立刻放弃当前 i。

3. 优化起点范围：若 i + m > n，后面再也放不下整段 needle，所以 i 只需从 0 到 n - m（n 为 haystack 长度）。

4. 内层用 j 从 0 到 m-1 比较 haystack[i+j] 与 needle[j]；若全程相等则返回 i，否则继续下一个起点。

5. 全部起点都失败则返回 -1。本题数据规模下暴力足够；KMP 等算法可把均摊复杂度降到 O(n+m)，但实现更重，简单题先掌握双下标模拟即可。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`i`	int	定义：`haystack` 中尝试作为匹配起点的下标维护：从 `0` 到 `n - m` 枚举每个可能起点更新：每轮外层循环 `i++`，直到找到匹配或枚举完毕
`j`	int	定义：当前正在比对的 `needle` 内偏移量维护：当 `haystack[i+j] == needle[j]` 时同步前进，否则本轮起点 `i` 失败更新：匹配成功则 `j++`；若 `j == m` 说明整段 `needle` 匹配完成
`m`	int	定义：`needle` 的长度维护：循环中用于判断「从 `i` 起是否还能放下整段 `needle`」以及「`j` 是否已扫完 `needle`」更新：初始化时 `m = len(needle)`，循环中不变

⌨️ 落码步骤

1. 令 n = len(haystack)，m = len(needle)

2. 外层 for i in range(n - m + 1)：以 i 为起点尝试匹配

3. 内层 j 从 0 到 m-1：若 haystack[i+j] != needle[j] 则跳出内层，换下一个 i

4. 若内层未提前跳出（j == m），说明匹配成功，返回 i

5. 所有起点均失败，返回 -1

💻 代码实现

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        for i in range(n - m + 1):          # 枚举每个可能的起点
            j = 0
            while j < m and haystack[i + j] == needle[j]:
                j += 1                      # 逐字符对齐 needle
            if j == m:                      # 整段 needle 匹配完成
                return i
        return -1

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        for (int i = 0; i <= n - m; i++) {  // 枚举每个可能的起点
            int j = 0;
            while (j < m && haystack[i + j] == needle[j]) {
                j++;                         // 逐字符对齐 needle
            }
            if (j == m) return i;            // 整段匹配完成
        }
        return -1;
    }
};
// 时间 O(n·m)，空间 O(1)

📈 复杂度分析

时间复杂度 O(n·m)

空间复杂度 O(1)

⚠️ 常见坑

❗ 外层循环边界是 i <= n - m（即 range(n - m + 1)），漏掉最后一个合法起点会错。

❗ 内层比较要用 haystack[i + j] 而不是 haystack[j]，起点偏移 i 不能丢。

❗ 匹配成功条件是 j == m（扫完整个 needle），不是 j == m - 1；提前 return i 前务必确认内层完整通过。

🔍 必测边界 Case

Case 1：needle 比 haystack 长

haystack = "a", needle = "aa" → -1（n - m + 1 <= 0，外层不执行）

Case 2：完全相等

haystack = "abc", needle = "abc" → 0（第一个起点即匹配）

Case 3：首字符相同但后续失败

haystack = "aaaaa", needle = "aab" → -1（多个起点共享前缀，需在第三位发现不等）