实现strStr()（28）

题目

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例

输入: haystack = "hello", needle = "ll" 输出: 2

输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

算法

indexOf()

export const strStr = (haystack, needle) => {
	return haystack.indexOf(needle);
};

滑动窗口

维护一个needle长度的窗口，在haystack中去查找该窗口内文字是否匹配needle，如果不匹配，则回溯到起始位置的下一位

export const strStr = (haystack, needle) => {
	for (let i = 0; i < haystack.length - needle.length + 1; i++) {
		if (haystack.substring(i, i + needle.length) === needle) return i;
	}
	return -1;
};

双指针

创建两个指针i、j分别指向haystack和needle的头部，然后依次向后查找字符是否匹配，如果匹配则继续移动；如果不匹配则i指针回溯至起始位置的下一位，j指针重置向needle的头部

export const strStr = (haystack, needle) => {
	if (needle === "") return 0;
	let i = 0,
		j = 0;
	while (i < haystack.length) {
		if (haystack[i] === needle[j]) {
			let haystackIndex = i;
			while (haystack[haystackIndex] && needle[j] && haystack[haystackIndex] === needle[j]) {
				haystackIndex++;
				j++;
			}
			if (j === needle.length) return i;
			j = 0;
		}
		i++;
	}
	return -1;
};