LeetCode 28. Find the Index of the First Occurrence in a String
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
len_needle = len(needle)
for i in range(len(haystack)):
if haystack[i] == needle[0]:
if len(haystack)-i < len_needle:
return -1
check = haystack[i:i+len_needle]
if check == needle:
return i
return -1
haystackの最初の文字とneedleの最初の文字が一致するようなhaystackのindexを探す
そのようなindexがあったら、そのindexからneedleの文字数分だけhaystackの文字列を抜き出してきて、その文字列(check)がneedleに一致するか調べる。
時間計算量はO(nm)
→for文はn回回る。
→checkとneedleの比較が文字列の長さ分(すなわちm)かかる
→n*m
空間計算量はO(n+m)
→haystackがn
→needleがm
→checkがm
→n+2mだが、係数は無視されるのでn+m