实现 strStr()
题目
难度级别：简单
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll" 输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
解题思路
变量i与k，i为当前遍历needle的一个索引，k为若在haystack找到与needle第一个值相等的一个索引。
遍历haysta判断i是否为0。
1.若i为0
判断当前遍历的haystack的项是否小于needle的长度。 若小于，则没有相等值，返回-1；若不小于且haystack的当前项与neelde的第i项值相等，则判断是否neelde的长度为1，若为1，直接返回j的索引，若i的长度不为1，则将j的值赋给k，继续遍历。
2.若i不为0
若haystack的当前项与needle的当前项相等，则i++，若其中索引j与k+1的差刚好等于needle的长度，那么已经匹配到值，直接退出循环；若haystack的当前项与needle的当前项不相等，则需要将j项返回至k的后一项继续遍历。
const strStr = function(haystack, needle) {
if (needle.length === 0) return 0
if (needle.length > haystack.length) return -1
let i = 0
let k = -1
for (let j = 0; j < haystack.length; j++) {
if (i === 0) {
if (haystack.length - j + 1 <= needle.length) {
return -1
}
if (haystack[j] === needle[i]) {
if(needle.length === 1){
return j
}
k = j
i++
}
}
else {
if (haystack[j] === needle[i]) {
if ((j - k + 1) === needle.length) {
break
}
i++
}else{
j = k
k++
i = 0
}
}
}
return k === haystack.length ? -1 : k
};题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-strstr
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录