Pythonで回文になる単語の連結パターンの数を求めるプログラム

互いに異なる単語のリストが与えられたとき、その中から2つの異なる単語を選んで連結し、回文（パリンドローム）を作ることができる組み合わせの総数を求める問題です。

例えば、入力が words = ["time", "emit", "mo", "m"] の場合、「timeemit」「emittime」「mom」の3通りが作れるため、出力は 3 になります。

解法のアプローチ

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

• 結果を格納する変数 res を 0 で初期化します。
• ln に配列内の単語の個数を代入します。
• k を 0 から 1 まで繰り返します。
  • i を 0 から ln − 1 まで繰り返します。
    • j を i + 1 から ln − 1 まで繰り返します。
      • words[i] と words[j] を連結した文字列が回文であれば 1、そうでなければ 0 を res に加算します。
  • 単語リストを逆順に入れ替えます。
• 最後に res を返します。

仕組みの解説

このアルゴリズムのポイントは、外側のループを2回回す点にあります。1回目のループでは「words[i] + words[j]」の順序で連結した場合をチェックし、リストを反転させた後の2回目のループでは、実質的に「words[j] + words[i]」という逆の順序での連結もカバーできます。これにより、すべてのペアについて両方向の連結パターンを漏れなく確認できるのです。

また、回文判定にはスライス記法 w3[::−1] を使って文字列を反転させ、元の文字列と一致するかどうかを比較しています。これはPythonらしい簡潔な回文判定の書き方です。

計算量については、単語の数を n、各単語の最大長を m とすると O(n² × m) となります。単語数が非常に多い場合はハッシュマップを活用したより効率的な手法もありますが、シンプルさと分かりやすさを重視するならこの方法が適しています。

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

実装例

class Solution:
    def solve(self, words):
        def is_palindrome(w1, w2):
            w3 = w1 + w2
            return w3 == w3[::−1]
        res = 0
        ln = len(words)
        for k in range(2):
            for i in range(ln):
                for j in range(i + 1, ln):
                    res += is_palindrome(words[i], words[j])
            words = words[::−1]
        return res
ob = Solution()
words = ["time", "emit", "mo", "m"]
print(ob.solve(words))

入力

["time", "emit", "mo", "m"]

出力

3