28.实现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()定义相符。本方法就是最原始的从头开始匹配,如果匹配错误则接着下一个点继续匹配。综合看来不是很好。
classSolution:
defstrStr(self,haystack:str,needle:str)->int:
hay_count=len(haystack)
_count=len(needle)
if_count==0:
turn0
i,j=0,0
whilei<hay_count:
ifhaystack[i]==needle[j]:
j+=1
i+=1
else:
i-=(j-1)
j=0
ifj==_count:
turni-j
turn-1相似的查找算法有KMP,BM,Horsool,之后有空在学一下这几种方法。