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

🟢   🔖  双指针 字符串 字符串匹配  🔗 力扣 LeetCode

题目

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"

Output: 0

Explanation: "sad" occurs at index 0 and 6.

The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"

Output: -1

Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

• 1 <= haystack.length, needle.length <= 10^4
• haystack and needle consist of only lowercase English characters.

题目大意

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

解题思路

思路一：原生方法

利用 JavaScript 提供的内置方法 indexOf，可以直接返回 needle 在 haystack 中的索引。

该方法会自动处理边界情况，若 needle 不存在，则返回 -1。

这种方法简洁高效，适合快速实现。

复杂度分析

• 时间复杂度： O(m * n)，其中 m 是 haystack 的长度，n 是 needle 的长度。最坏情况下，indexOf 需要遍历整个 haystack 并在每个位置比较 needle。
• 空间复杂度： O(1)，不需要额外的空间，使用内置方法。

---

思路二：手写 indexOf

若不能使用原生方法，则手动实现一下 String.prototype.indexOf() 方法，注意几个优化的细节。

• 首先，获取 haystack 和 needle 的长度，并检查 haystack 是否比 needle 短，如果短，则直接返回 -1。
• 使用一个 for 循环遍历 haystack，对于每个可能的起始位置，利用 slice 方法提取子字符串并与 needle 比较。
• 一旦找到匹配的子字符串，则返回当前的索引。
• 如果遍历结束仍未找到，返回 -1。

复杂度分析

• 时间复杂度： O(m * n)，其中 m 是 haystack 的长度，n 是 needle 的长度。对于每个起始位置，最多需要进行 n 次比较。
• 空间复杂度： O(1)，只使用常数空间，不需要额外的数据结构。

代码

原生方法

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
	return haystack.indexOf(needle);
};

手写 indexOf

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
	let len = haystack.length,
		n = needle.length;
	if (len < n) {
		return -1;
	}

	for (let i = 0; i <= len - n; i++) {
		if (haystack.slice(i, i + n) === needle) {
			return i;
		}
	}

	return -1;
};

相关题目

题号	标题	题解	标签	难度
214	最短回文串		字符串 字符串匹配 哈希函数 1+
459	重复的子字符串	[✓]	字符串 字符串匹配