よしたく blog

ITエンジニアとして自分が知らなかったことをまとめています

【LeetCode】14.longest-common-prefix をPythonで解く

問題はこちら

leetcode.com

Example 1:

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

問題の解説に載っている例を持ってきた。 リストの中に格納されている複数の文字列を、前から 1 文字ずつ取り出していく。 取り出した文字が同じかどうかを判定し、同じなら 2 文字目へ、違うのならば同じ部分だけを出力するものになる。

回答例はこのようになる。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = ""
        if not strs:
            return prefix

        for i in zip(*strs):
            if len(set(i)) == 1:
                prefix += i[0]
            else:
                return prefix

        return prefix

解説

空文字の判定

そもそも送られてくるstrsがからの場合は空文字を返す。

prefix = ""
if not strs:
    return prefix

forで回して、文字の判定

for i in zip(*strs):
    if len(set(i)) == 1:
        prefix += i[0]
    else:
        return prefix

まずzip関数を使う。 引数にリストを指定し、iにタプルの形で受け取っている。 Example 1のstrs = ["flower","flow","flight"]だと、1回目のループ処理でiは(f,f,f)を受け取る。

次にif文の部分になる。 set(i)で、タプルになっているiをセット型にしている。 set型は値を重複して持たないので、同じ文字は1つにまとめられる。 Example 1では、iが(f,f,f)となっていたが、{f}になる。 {f}となっている要素をlen関数を使って中身の数を確認し、1ならprefixに格納している。

今回はいくつかの文字列が、先頭からどこまで同じかを確認する問題だった。 つまり、len関数を使った時に1以外の数が返ってくれば、同じ文字ではないということになるので、それ以降は確認する必要がない。