🖋

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

に公開
Python
LeetCode
tech

はじめに

LeetCode 「28. Find the Index of the First Occurrence in a String」の問題を Python3 で解きました。

問題

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

問題文

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.

和訳
2 つの文字列 needleと haystack を指定すると、haystack 内で needleが最初に出現するインデックスを返します。needleが haystack の一部でない場合は -1 を返します。

例

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.

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

制約

  • 1 <= haystack.length, needle.length <= 104
  • haystack and needle consist of only lowercase English characters.

解答

haystackの中にneedleの文字の先頭が現れたときに、それ以降の文字がneedleと一致するかが判定できれば答えを導くことができます。
当初以下のようなコードを考えました。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(haystack) < len(needle):
            return -1

        for i, ch in enumerate(haystack):
            if ch == needle[0]:
                if haystack[i:i+len(needle)] == needle:
                    return i

        return -1

上記でも通りますが、haystackの最後まで確認しまっています。
実際はneedleが収まる範囲まで確認できれば良いです。

例えば、以下の場合はhaystack[8]（最後のaの位置）以降は確認する必要がないです。

haystack = "sadbutsad", needle = "sad"

それを踏まえて以下のように改善できます。

コード

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

len(haystack) - len(needle) + 1でneedleが収まる範囲にしています。

計算量

  • 時間的計算量：O(n*m)
  • 空間的計算量：O(1)
GitHubで編集を提案

Discussion