0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

LeetCode / Implement strStr()

Posted at

ブログ記事からの転載)

[https://leetcode.com/problems/implement-strstr/]

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Pythonから入った私は知らなかったのですが、strstr関数というのはCやPHPで使われる「文字列から文字列を検索してその場所のポインタを返してくれる関数」だそうです。このstrstr関数を実装しなさい、という問題です。
そしてまたClarificationがポイントで、マッチングする文字列が空の場合は0を返すように実装する必要があります。

解答・解説

解法1

マッチングする文字列が空の場合に0を返すためにif文を入れたくなりますが、その欲求に争いつつ、できるだけシンプルに処理したコードが以下です。

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

可読性は高いと思いますが、リストのスライスはリストのコピーを生成するため、時間計算量はhstackのサイズをhとしたときに最大で[tex: O(n * h)]に達してしまいます。

解法2(のreference)

KMP法というアルゴリズムがあるようで、このアルゴリズムは一度照合した文字列を再度照合することはしないというアルゴリズムなので、時間計算量は高々[tex: O(n)]に抑えられるようです。
実装はちょっと難解で、余力のあるときにやります。。。ひとまずreferenceだけ示します。

[http://sevendays-study.com/algorithm/ex-day2.html]

ただ、処理が複雑になるため、計算量が解法1を上回るかというと、そうでもないようです。

0
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?