どーも！
たかぽんです！
LeetCode二日目です。
今回はLongest Common Prefixをやってみました！
では、それについてです...!
Longest Common Prefix
では、まず最初に問題の簡単な解説を。
問題としては最も長い共通する接頭辞（文字列の先頭から見ていって一致する部分）を抜き出す...というものです。
例えば...
上記の問題ページでも解説されていますが...
Input: strs = ["flower","flow","flight"]
Output: "fl"上記のように三つの単語すべてで最初の始まり箇所は"fl"となっています。
そのため、今回の回答は"fl"になります。
このように、さまざまな文字列が入っているリスト中から、それぞれの文字で一致する部分を探すわけですね！
最初アルゴリズムもなんとなーくで解いたんですが、だいぶん沼にハマりました...w
なんとかクリアはできたんですが、正直言うと最悪です...w
2時間ちょっとかかったのですが、多分アルゴリズムあんまり整理できていないし、可読性なんて知ったこっちゃない...!って感じです...w
回答を提出する際、このテストデータだと通らなかったよー！
とかお知らせしてくれるんですが、それで気づいて、じゃぁif文一個追加して....
といった感じでやったので、絶対よろしくないフラグ使ってたり、同じ処理描きまくってたり...もうつぎはぎですね...
一応、僕が考えた流れをお伝えすると、まず最初は一番最初のリストの文字列(str[0])から他の要素を比較して、一致しない分を引いていって、最終的に残った文字列が答えになるだろう...と言う感じでスタートしました。
targetには最終的な答えになる文字列を保持するようにし、一番最初の文字列"flower"と、その次の文字列から、"flow"の"f"を最初に比較します。
その次は"f"がOKだったので、"fl"、そして"flo"、最後に"flow"といった流れです。
そして、文字列全体を比較し、問題ない場合はtargetにその一致した分を入れ、比較ようの値を初期化...といった形です。
ただ、先程お伝えした通り、ちょっと納得はできない感じになってしまったので、いつかリベンジしたいですね...
ちなみに、こう言うものの場合、アルゴリズムでしっかり考えた上で実装着手したほうがいいのか、実装しながらアルゴリズム理解していくのがいいのか、どっちなんでしょうか...そういったところも肌で学んでいくしかないか...!
これはそのうちリベンジすると思います！
最後にお恥ずかしいですが、コードも貼っておきます...!
実際に提出したコード
こんなのでも、ちょびっと処理速度早いらしい...
一応動きはしますが、コード自体は参考にしないことを推奨します...!
Runtime: 180 ms, faster than 6.30% of Python3 online submissions for Longest Common Prefix.
Memory Usage: 14.4 MB, less than 57.53% of Python3 online submissions for Longest Common Prefix.class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
target = ''
checkstr = ''
tmpstr = ''
flag = 0
nomatchflag = 0
# 文字列がそもそも一つの場合はその要素を返す
if len(strs) == 1:
return strs[0]
for sentence in strs:
if sentence == '':
target = ''
break
for index,word in enumerate(sentence):
# targetが空なら初回のみ文字を入れる
if target == '':
target = strs[0]
tmpstr = checkstr + word
if target.find(tmpstr) != 0 :
if index == 0:
nomatchflag = 1
target = checkstr
checkstr = ''
tmpstr = ''
break
checkstr = tmpstr
flag = 1
if tmpstr == sentence:
target = checkstr
checkstr = ''
tmpstr = ''
if flag != 1 :
target = ''
if nomatchflag == 1 :
target = ''
return target