LeetCode解説　一日一問　14. Longest Common Prefix

LeetCodeって？
問題
回答
コード
結果

LeetCodeって？

Just a moment...

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

Pythonではじめるアルゴリズム入門伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井敏克 ]

問題

Just a moment...

タイトル：14. Longest Common Prefix

難易度：Easy

内容：

複数の単語が入ったリスト strs が与えられる。strs 内の単語すべてに共通する接頭語を返す。
共通するものがない場合は “” を返す。

例：

strs = ["flower","flow","flight"]
返り値: "fl"

strs = ["dog","racecar","car"]
返り値: ""

回答

簡単なのであまり解説の余地がないです。

返り値は、最も短い単語以上になることはないので、まずは最も短い単語を探します。

min_str = min(strs, key = len)

あとは、min_str とほかの単語がどこまで一致するかを確認するだけです。

コード

上記の理論を実装します。

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        min_str = min(strs, key = len) # strsの中で最も長さが短い単語
        
        for i, l in enumerate(min_str): # min_strを1文字ずつ確認
            for j in range(len(strs)): # すべてのstrsの単語について
                if l != strs[j][i]: # min_strのi文字目と一致しなかったら
                    return min_str[0:i] # 一致したとこまでを返す
        return min_str # 完全一致ならmin_strを返す

計算量はO(N²)です。

コードはgithubにも保管しています。