Pythonで文字列配列の最長共通プレフィックスを求める方法

配列に複数の文字列が格納されている場合、それらの文字列に共通する最長共通プレフィックス（Longest Common Prefix）を見つける必要があります。ここでは、すべての文字列が小文字であると仮定します。また、共通のプレフィックスが存在しない場合は空文字列 "" を返すものとします。

例えば、文字列の配列が ["school", "schedule", "scotland"] のような場合、すべての文字列に共通して含まれているのは "sc" であるため、最長共通プレフィックスは "sc" となります。

解決のアプローチ

この問題を解くためには、以下の手順で処理を進めます。

1. 最初の文字列を基準（current）として設定します。
2. 配列内の残りの各文字列を取り出し、1文字ずつ順番に比較していきます。
3. 基準となる文字列と比較対象の文字列の文字が一致すれば次の文字へ進み、一致しなければループを抜けます。
4. ループを抜けた時点で、一致した部分までの部分文字列を新しい基準（current）として更新します。

この処理をすべての文字列に対して繰り返すことで、最終的に残った current が最長共通プレフィックスとなります。

Pythonでの実装例

それでは、実際のコード実装を見てみましょう。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        current = strs[0]
        for i in range(1, len(strs)):
            temp = ""
            if len(current) == 0:
                break
            for j in range(len(strs[i])):
                if j < len(current) and current[j] == strs[i][j]:
                    temp += current[j]
                else:
                    break
            current = temp
        return current

input_list = ["school", "schedule", "scotland"]
ob1 = Solution()
print(ob1.longestCommonPrefix(input_list))

入力

["school", "schedule", "scotland"]

出力

"sc"

コードの解説

• 空配列のチェック： 配列が空の場合は即座に空文字列を返します。
• 初期化： 配列の最初の文字列を current として設定し、これを比較の基準とします。
• 早期終了： current が空になった時点で、共通プレフィックスが存在しないことが確定するため、ループを抜けて処理を終了します。
• 文字ごとの比較： 各文字列について先頭から1文字ずつ current と比較し、一致した文字だけを temp に追加していきます。

このアルゴリズムの計算量は、最悪の場合 O(S) となります（S は全文字列の文字数の合計）。文字列の数が多くても、共通プレフィックスが短い場合は早期に処理が終了するため、効率的に動作します。