题目描述
实现 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() 定义相符。
我的解法——双循环(AC)
- 两层循环
- 时间空间复杂度均为O(mn)。
- Beat37%
class Solution:
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if(len(haystack) - len(needle) < 0):
return -1
for i in range(len(haystack) - len(needle) + 1):
flag = True
for j in range(len(needle)):
if(haystack[i + j] != needle[j]):
flag = False
break
if(flag):
return i
return -1
最优解法——KMP算法
- 参考讲解:
- 清华大学 邓俊辉:http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184_2X+sp/courseware/4c294e9ea5b5433d831443e64f64bacb/5c4a944aba1f4c9e996f555f7f9b76cb/
- https://blog.csdn.net/v_july_v/article/details/7041827
def strStr(self, haystack, needle):
if haystack == None or needle == None:
return -1
m, n = len(haystack), len(needle)
#generate next array, need O(n) time
i, j = -1, 0
next = [-1] * n
while j < n - 1:
# needle[i] stands for prefix, neelde[j] stands for postfix
# 考虑next[j]和next[j + 1]的递推关系
# 1.P[i] == P[next[i]]时,next[i + 1] = next[i] + 1
# 2.P[i] != P[next[i]]时,i = next[i],直至满足条件1时套用1,这个序列严格递减,并且必定收敛于next[0] = -1
if i == -1 or needle[i] == needle[j]:
i, j = i + 1, j + 1
next[j] = i
else:
i = next[i]
print i,j,next[i],next[j]
#check through the haystack using next, need O(m) time
i = j = 0
while i < m and j < n:
if j == -1 or haystack[i] == needle[j]:
i, j = i + 1, j + 1
else:
j = next[j]
if j == n:
return i - j
return -1