Pythonで文字列リストの最長共通プレフィックス(接頭辞)を求めるプログラム

小文字で構成された文字列のリストが与えられたとき、その中に共通して含まれる最長の共通プレフィックス(接頭辞)を見つける問題を考えてみましょう。

例えば、入力が ["antivirus", "anticlockwise", "antigravity"] の場合、すべての文字列に共通する先頭部分は "anti" なので、出力は "anti" となります。

解決のためのアプローチ

この問題は、以下の手順で解くことができます。

1. まず、リスト words をアルファベット順にソートします。これにより、辞書順で最も近い文字列同士が隣り合うため、比較が効率的になります。
2. 共通プレフィックスを格納するための新しいリスト prefix を用意し、フラグ変数 flag を 0 で初期化します。
3. i を 0 から words[0] の長さまで繰り返します。
   • 各反復で、words[0][i] の文字を prefix に追加します。
   • 次に、words 内のすべての文字列 j について、j[i] が prefix の末尾の文字と一致するかを確認します。
     • 一致しない場合は、prefix の末尾の要素を削除し、flag を 1 に設定して、内側のループを抜けます。
   • flag が 1 になっている場合は、外側のループも抜けます。
4. 最後に、prefix リスト内のすべての文字を連結した文字列を返します。

実装例

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

class Solution:
   def solve(self, words):
      words.sort()
      prefix = []
      flag = 0
      for i in range(len(words[0])):
         prefix.append(words[0][i])
         for j in words:
            if j[i] != prefix[-1]:
               prefix.pop()
               flag = 1
               break
         if flag == 1:
            break
         return ''.join(prefix)
ob = Solution()
words = ["antivirus", "anticlockwise", "antigravity"]
print(ob.solve(words))

入力

["antivirus", "anticlockwise", "antigravity"]

出力

anti

コードのポイント

• ソートの役割: リストをソートすることで、最初の文字列と他の文字列の差分が最小限になり、早期に不一致を検出できます。
• フラグによる二重ループの制御: Pythonではラベル付きbreakが使えないため、flag 変数を利用して外側のループもまとめて終了させています。
• 計算量: 最悪の場合でも O(S) です。ここで S は全文字列の文字数の合計です。

このように、シンプルなループ処理とソートを組み合わせることで、複数の文字列から効率的に最長共通プレフィックスを抽出することができます。