# LeetCode Easy 28. Implement strStr()

tags: leetcode

問題

• Explore
• Problems

アイデア

｢2つの文字列を与えられた時，片方の文字列haystackに別の文字列needleが含まれているなら，needleがhaystackのどの位置から始まるか添字を返せ｣という問題です．

needleが空文字のときは0を返します．

愚直に実装すれば良いと思います．

解法

• 全探索します

計算量

文字列の長さをそれぞれ$N$，$M$とします．

• 時間計算量
  • $O(NM)$
• 空間計算量
  • $O(1)$

Python

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