前言

❤️笔芯❤️~

28. 实现 strStr()

一、题目描述

实现 strStr() 函数。

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

1
2
3
4
5
输入: haystack = "hello", needle = "ll"
输出: 2

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

说明:

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

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

二、思路分析

当两字符串相等时,返回0

haystack 为空串时,返回-1

needle 为空串时,返回0

needle 的长度大于 haystack 返回-1

循环 haystacki记录其指针。和 needle 的第一位进行相等判断,当一样时,开始循环 needlej记录其指针。res记录相等时的i指针,即结果。

i和j加一,继续循环。

如果之后全相等,中间没有出现不等的情况。(hello,ll)那么当j和needle的长度相等了,就跳出循环。

如果中间出现不相等,那么i就返回res记录的下一位置,继续循环,res和j重置。继续对比 noodle 的第一个字符。

重复上述步骤,当j和len相等就说明匹配到了,跳出循环;i等于haystack长度,即haystack循环完毕后,j还不等于len,那么就是没找到,res重置,跳出循环。

三、答案代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var strStr = function(haystack, needle) {
if(haystack===needle) return 0
if(haystack==="") return -1
if(needle==="") return 0
if(needle.length>haystack.length) return -1
var j=0,i=0,res=-1

while(i>=0){
var c=haystack[i]
var len=needle.length
if(j===len) break
if(i==haystack.length){
if(j<len){
res=-1
}
break
}

if(c===needle[j]){
j++
if(res===-1) res=i
i++
}else{
if(res>-1){
i=res+1
j=0
res=-1
}else{
i++
}

}
}

return res
};

四、总结

  1. 实现 strStr()题解

回看笔者往期高赞文章,也许能收获更多喔!

❤️关注+点赞+收藏+评论+转发❤️,原创不易,鼓励笔者创作更好的文章