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

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

問題文
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

"""
Assume
 We have to check longest common prefix from first element.
 We don't have to check from second element onwards.
 The length of each element of strs is less than 200.
 The number of elements of strs are at most 200.

Test case
 ["dog", "do" ]
 ["fog","dog"]
 ["flower", "flowlence", "fluent"]

Solution
 1. brute force
  Iterate n times. n is the number of first element of strs. This is outer loop.
  And Iterate each element of strs. This is inner loop.
  In each iterate, We check the outer iterator's value is equal to the number of inner iterater.
  
"""

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        lcp = ""
        #Start a for loop iterate over each literal of first element.
        for i in range(len(strs[0])):
            #Start a for loop iterate over each element of strs.
            for s in strs:
                #Check if the length of s is equal to i which means end of arrive at the end of s.
                #And Check simaltaneously if i-th element of s and strs are not equal.
                if i==len(s) or s[i]!=strs[0][i]:
                    #As we can't add letter no more, return lcp.
                    return lcp
            #Add the i-th letter of strs' first element.
            lcp += strs[0][i]
        return lcp

"""

Assume

We have to check longest common prefix from first element.

We don't have to check from second element onwards.

The length of each element of strs is less than 200.

The number of elements of strs are at most 200.

Test case

["dog", "do" ]

["fog","dog"]

["flower", "flowlence", "fluent"]

Solution

1. brute force

Iterate n times. n is the number of first element of strs. This is outer loop.

And Iterate each element of strs. This is inner loop.

In each iterate, We check the outer iterator's value is equal to the number of inner iterater.

"""

class Solution:

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

lcp = ""

#Start a for loop iterate over each literal of first element.

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

#Start a for loop iterate over each element of strs.

for s in strs:

#Check if the length of s is equal to i which means end of arrive at the end of s.

#And Check simaltaneously if i-th element of s and strs are not equal.

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

#As we can't add letter no more, return lcp.

return lcp

#Add the i-th letter of strs' first element.

lcp += strs[0][i]

return lcp

・チェックするのは1文字目からの共通部分だけでよい。

・途中から共通する文字列があってもそれはカウントしなくても良い。

・ただし、レベルアップした問題としてそれが出題される可能性はあるかもしれない。

・strsの1つ目の要素が持つ各文字列を外側のループにする

・内側のループでstrsの各要素を探索する。

もし、内側のループで今探索中の要素の長さと、i(1つ目の要素のi番目)が一致した場合、

既にstrsの1要素で終端に達したことになり、それ以上はlongest common prefixを追加できないので、その時点で返す。

または、内側のループで探索中の要素のi番目の文字と、外側ループ(1つ目の要素)のi番目の要素が一致していない場合も、lcpに文字を加えられないのでその時点で返す。

・最後まで探索を終えることができた場合はlcpを返す。(この場合は全ての要素が同じ文字列ということになるはず)

補足・参考・感想

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

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

記事一覧：LeetCode記事一覧