#はじめに
こんばんは.
M1就活生がLeetCodeから,easy問題を中心にPythonを用いて解いていきます.
↓では,解いた問題のまとめを随時更新しています.
まとめ記事
#問題
今回解いたのは,難易度easyから 問題28のImplement strStr() です.
問題としては,入力文字列haystack
の中に,もう一方の入力文字列needle
が最初に出現したインデックスを返すというもの.needle
がhaystack
に含まれていない場合は-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を返します.その後,繰り返し処理で,haystack
をlen(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にもあげておきます.