LeetCodeを1日1題解いてみる (day6)

6日目に取り組んだ問題はこちら！

28. Find the Index of the First Occurrence in a String

問題文

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.

僕の回答(失敗作)

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

僕の回答をGPTで修正

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        i = 0
        idx = 0
        while idx < len(haystack):
            if needle[i] == haystack[idx]:
                i += 1
                idx += 1
                if i == len(needle):
                    return idx - i
            else:
                if i > 0:  # 部分一致が失敗した場合
                    idx = idx - i + 1  # idx を調整して戻す
                else:
                    idx += 1
                i = 0 
        return -1

より効率の良い回答例

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

コメント

はじめ、haystack 内で部分一致が失敗した後、失敗した部分の次の位置から再探索していました。しかし、失敗した箇所の一部をもう一度探索する必要があることを見落としていました。
例えば、haystack = "ababc" と needle = "abc" のケースでは、idx = 2 の時点で haystack は "aba" となり部分一致に失敗します。この場合、私は4文字目のb から探索を再開していました。しかし、正しい処理では、失敗した箇所の2文字目の b から再度探索し直す必要がありました。
また、substring = haystack[i: i + len(needle)]で複数要素を一気に取り出せることを学びました😊

次回はこちら!