28. Find the Index of the First Occurrence in a String

🟠   🔖  双指针 字符串 字符串匹配  🔗 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 。

解题思路

解法一：原生方法

直接调用 JS 中 String.prototype.indexOf() 方法.

解法二：手写 indexOf

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

代码

原生方法

/**
 * @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. 最短回文串
• 459. 重复的子字符串

- [214. 最短回文串](https://leetcode.com/problems/shortest-palindrome)
- [459. 重复的子字符串](https://leetcode.com/problems/repeated-substring-pattern)