Problem

String Matchingに関する問題です。

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack

この問題では、haystack (干し草の山）と呼ばれる文字列の中から、needle(縫い針)と呼ばれる文字列が含まれるかどうかを判定します。参考までに、A needle in a haystackはイディオムで、広大な干し草の山の中からneedle縫い針を探すことから、「至難の業」「針の穴に糸を通すよう」といった意味になります。

InputとOutputの例は次になります。

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Approach 1

Naïveな方法として、下記のような回答を考えました。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

繰り返しの回数に気をつけてください。例えば、haystack="abcde"(5文字), needle="xyz" (3文字)の場合、繰り返す必要がある回数は3回になります。この３回というのは、「haystackの文字数 5 - needleの文字数 3 + 1 」となります。

この解法では、計算量は下記の様になります。

Time complexity: O(NM)
Nはhaystackの長さ、Mはneedleの長さとしています。
Space complexity: O(M)
haystack[i:i+len(needle)]という箇所で、Pythonのスライシング処理を用いているためです。
面接官によっては、Space complexityでより効率性を求める解法に誘導するかもしれません。その場合は、下記のApproach 2のように対応します。

Approach 2

Approach 1のスライシングの代わりに、一文字ずつ比較をして確認をします。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle)+1):
            for j in range(len(needle)):
                if haystack[i+j]  != needle[j]:
                    # 内側のループからbreak
                    break 
                
                if j == (len(needle) -1):
                    return i
        return -1

この解法では、Time complexityはApproach #1と同じくO(NM)ですが、Space complexity はスライシングを使っていないのでO(1)になっています。

Reference

Rabin-Karp Algorithm 等のアルゴリズムについては、別の機会にします。