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