【LeetCode】14. Longest Common Prefix 解答・解説【Python】

LeetCodeの問題を解きます。問題文は翻訳サイトと私の拙い英語力で和訳しており、正確でない可能性が高いためご注意ください。

問題文
1. 原文
2. 和訳
方針
解答
1. コメント＋コード
2. コードのみ
補足・参考・感想

問題文

原文

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"] Output: "fl"

1
2

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

1
2
3

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

1 <= strs.length <= 200

0 <= strs[i].length <= 200

strs[i] consists of only lowercase English letters.

和訳

文字列の配列から、最長共通文字列を見つける関数を書いてください。

もし共通する文字列がない場合は、””を返してください。

例1:

Input: strs = ["flower","flow","flight"] Output: "fl"

1
2

Input: strs = ["flower","flow","flight"]
Output: "fl"

例2:

Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

1
2
3

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

例2では共通する文字列はありません。

制約

strsの要素数は1~200

strsの各要素の文字数は0~200

strsのi番目の要素は英語の小文字のみを含む

方針

・計算量は200文字が200要素あるので、40000=4*10^4でしょうか。

・strsの1つ目の要素について、i文字目がstrsの各要素のi文字目と一致するかをfor文で確認していきます。

解答

コメント＋コード

#クラスを定義
class Solution:
    #関数を定義。strsはstr型の要素を持つリスト、返り値はstr型
    def longestCommonPrefix(self, strs: List[str]) -> str:
　　　　#【1】strsの各要素の文字数が小さい順から並べ替える。
        strs = sorted(strs, key=len)
　　　　#strsの全要素で共通する文字を格納する変数resを用意
        res = ""
　　　　#strsの1つ目の要素について、1文字目から順に全ての文字をfor文で処理する
        for i in range(len(strs[0])):
　　　　　　 #strsの要素全てに対してfor文で処理する
            for s in strs:
　　　　　　　　　#【2】iが1つ目の要素の文字数と一致した場合、もしくはs[i]と1つ目の要素のi番目の文字と不一致の場合
                if i == len(s) or s[i] != strs[0][i]:
　　　　　　　　　　　#resを返す
                    return res
　　　　　　#【3】1つ目の要素のi番目の文字が、全ての要素のi番目の文字と一致した場合は、その文字をresに加える
            res += strs[0][i]
　　　　 #【4】全ての文字が一致した場合はresを返す
        return res

#クラスを定義

class Solution:

#関数を定義。strsはstr型の要素を持つリスト、返り値はstr型

def longestCommonPrefix(self, strs: List[str]) -> str:

　　　　#【1】strsの各要素の文字数が小さい順から並べ替える。

strs = sorted(strs, key=len)

　　　　#strsの全要素で共通する文字を格納する変数resを用意

res = ""

　　　　#strsの1つ目の要素について、1文字目から順に全ての文字をfor文で処理する

for i in range(len(strs[0])):

　　　　　　 #strsの要素全てに対してfor文で処理する

for s in strs:

　　　　　　　　　#【2】iが1つ目の要素の文字数と一致した場合、もしくはs[i]と1つ目の要素のi番目の文字と不一致の場合

if i == len(s) or s[i] != strs[0][i]:

　　　　　　　　　　　#resを返す

return res

　　　　　　#【3】1つ目の要素のi番目の文字が、全ての要素のi番目の文字と一致した場合は、その文字をresに加える

res += strs[0][i]

　　　　 #【4】全ての文字が一致した場合はresを返す

return res

【1】文字列の並び替え

テストケース1では、入力されるstrsの各要素は[“flower”,”flow”,”flight”]です。

各要素の内、文字数が一番短い単語の文字数が最長共通文字列(LCP)となると思いました。

1つ目のfor文では、strsの1つ目の要素のi番目の文字に対して、strsの各要素のi番目の文字が一致するかを調べています。

そのため、文字数が一番短い単語を1番目の要素にすることで、処理を短くできるのではないかと考えました。ただ、各要素の文字数が全て少なかったり、文字数の差が小さい場合は逆に並べ替えにかかる時間でロスしてしまうかもしれません。

【2】1つ目の要素の文字数と一致した場合というのは、テストケース1ではiが4になった場合です。

strsを文字数の短い順に並べ替えたので、1つ目の要素は”flow”ですが、strs[0][3]の時点で”w”までのチェックが完了しているので、i=4、つまりstrs[0][4]はもう調べることができないためreturnします。

また、strsのs番目の要素のi番目の文字(s[i])と、strsの1つ目の要素のi番目の文字(strs[0][i])が不一致というのは、テストケース1では”o”に当たります。”fl”までは3つの要素が一致しましたが、”o”は”flight”の3番目の要素とは異なるため、returnします。

【3】1つ目の要素のi番目の文字が、strsの各要素のi番目の文字と一致したというのは、テストケース1では、”f”と”l”になります。2個目のfor文内のifに該当しなかった場合であり、全ての要素で共通する文字だったため、”res”に”f”(1つ目のfor文の2回目のループでは”l”)を加えて次の文字に移ります。

【4】は1つ目の要素の文字列が、strsの全要素の文字列と一致した場合です。

テストケース1では該当しませんが、[“flow”,”flow”,”flow”]は該当する一例になると思います。また、[“flow”,”flowe”,”flower”]のように、一番文字数の短い要素を、全ての要素が持つ場合も該当するかと思います。

コードのみ

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs = sorted(strs, key=len)
        res = ""
        for i in range(len(strs[0])):
            for s in strs:
                if i == len(s) or s[i] != strs[0][i]:
                    return res
            res += strs[0][i]
        return res

class Solution:

def longestCommonPrefix(self, strs: List[str]) -> str:

strs = sorted(strs, key=len)

res = ""

for i in range(len(strs[0])):

for s in strs:

if i == len(s) or s[i] != strs[0][i]:

return res

res += strs[0][i]

return res

補足・参考・感想

わからなかったので答えを見ました。実際のコーディング面接では時間が限られているでしょうし、解き方がわからない問題に対してどうやって臨むか、考えを整理して口に出しながら受けられるようにしたいなと思います。

今後、計算量を考えるようにしていきたいと思います。思いっきり間違えると思いますが、それも含めてコーディング試験の練習と考えます。

記事一覧：LeetCode記事一覧