てくてくテック

【LeetCode】14. Longest Common Prefix (二日目)

leetcode

どーも!

たかぽんです!

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
                
モバイルバージョンを終了