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 等のアルゴリズムについては、別の機会にします。