0
1

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 3 years have passed since last update.

【LeetCode】就活に向けたコーディングテスト対策 #10

Last updated at Posted at 2021-06-19

#はじめに
こんばんは.
M1就活生がLeetCodeから,easy問題を中心にPythonを用いて解いていきます.

↓では,解いた問題のまとめを随時更新しています.
まとめ記事

#問題
今回解いたのは,難易度easyから 問題28のImplement strStr() です.
問題としては,入力文字列haystackの中に,もう一方の入力文字列needleが最初に出現したインデックスを返すというもの.needlehaystackに含まれていない場合は-1を返し,needleがからの場合は0を返します.

入力例と出力例は以下の通りです.

Example 1:

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

Example 2:

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

Example 3:

Input: haystack = "", needle = ""
Output: 0

#書いたコード
まず,needleが空かどうか判定し,空であれば0を返します.その後,繰り返し処理で,haystacklen(needle)の長さでずらしていきながら,needleと一致すればそのインデックスを返します.最後まで一致するものが見つからない場合に-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[i:i+len(needle)]は,len(needle)に依存してメモリを使用するためあまり良くない解だという議論を見かけました.そのため,needleが長い場合には他の解法で解いたほうが良さそうです.

#おわりに
とりあえず,最後まで解いてみることが大事だという考えですが,余裕があればさらに良くなる改善策についても考えてみたいです.今後も他の方の解法や,コメントなども参考に,何が良くて何がダメなのか,何故そうなるのかなど,深く考えていきます.

今回書いたコードはGitHubにもあげておきます.

前回 次回

0
1
0

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
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?