Easy

题目描述

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= haystack.length, needle.length <= 10^4
  • haystack 和 needle 仅由小写英文字符组成

解题思路

这是经典的字符串匹配问题，有多种解法：

方法一：暴力匹配（推荐）

最直观的方法是枚举所有可能的起始位置，对每个位置检查是否能完全匹配子串。从 haystack 的每个位置开始，尝试匹配 needle 的所有字符。如果某个位置的字符不匹配，则跳到下一个起始位置继续尝试。

方法二：KMP算法

对于更复杂的场景，可以使用KMP（Knuth-Morris-Pratt）算法。KMP通过预处理模式串构建部分匹配表（next数组），避免不必要的回溯，将时间复杂度优化到O(m+n)。

方法三：内置函数

大多数编程语言都提供了字符串查找的内置函数，如C++的find()、Python的find()等，这些函数通常经过高度优化。

对于本题的数据规模（长度不超过10^4），暴力匹配已经足够高效且容易理解实现。代码给出暴力匹配的解法，时间复杂度O(m×n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.length();
        int n = needle.length();
        
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            while (j < n && haystack[i + j] == needle[j]) {
                j++;
            }
            if (j == n) {
                return i;
            }
        }
        
        return -1;
    }
};

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        m, n = len(haystack), len(needle)
        
        for i in range(m - n + 1):
            j = 0
            while j < n and haystack[i + j] == needle[j]:
                j += 1
            if j == n:
                return i
        
        return -1

public class Solution {
    public int StrStr(string haystack, string needle) {
        int m = haystack.Length;
        int n = needle.Length;
        
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            while (j < n && haystack[i + j] == needle[j]) {
                j++;
            }
            if (j == n) {
                return i;
            }
        }
        
        return -1;
    }
}

var strStr = function(haystack, needle) {
    const m = haystack.length;
    const n = needle.length;
    
    for (let i = 0; i <= m - n; i++) {
        let j = 0;
        while (j < n && haystack[i + j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度暴力匹配KMP算法
时间复杂度O(m×n)O(m+n)
空间复杂度O(1)O(n)

其中 m 为 haystack 的长度，n 为 needle 的长度。

相关题目