Pythonでリスト内の文字列を連結して指定した文字列が作成できるか判定する方法

プログラミングでは、リストに含まれる複数の文字列を組み合わせて、目的の文字列が作成できるかどうかを確認したい場面があります。このとき、リスト内の文字列をどのような順序で連結してもよいという条件が付くことがあります。

本記事では、Pythonを使ってこの問題を解決する2つの方法、「順列（permutations）」を使う方法と「正規表現」を使う方法について、具体的なコード例とともに解説します。

方法1：itertoolsのpermutationsを使う

標準ライブラリのitertoolsモジュールには、順列を生成するpermutations関数が用意されています。この関数を使うと、リスト内の文字列をさまざまな順序で組み合わせたパターンをすべて取得できます。

生成された組み合わせを順番に連結し、目的の文字列と一致した時点で「作成可能」と判断できます。

コード例

from itertools import permutations

chk_str = 'balloon'
Alist = ['fly','on', 'o', 'hot', 'ball', 'air']

def findstring(strchk, biglist):
    for i in range(2, len(biglist) + 1):
        for perm in permutations(biglist, i):
            if ''.join(perm) == strchk:
                return True
    return False

# 関数を使用
if(findstring(chk_str,Alist)):
    print("String can be formed.")
else:
    print("String can not be formed.")

実行結果

String can be formed.

上記のコードでは、リストから2個以上の要素を選んで順列を生成し、それぞれを連結してチェック対象の文字列「balloon」と一致するか確認しています。「ball」「o」「on」をこの順序で連結すると「balloon」になるため、Trueが返されます。

方法2：正規表現（reモジュール）を使う

reモジュールのcompile関数を使う方法もあります。リスト内の各文字列を|（OR条件）でつなぎ、それらを繰り返しマッチさせる正規表現パターンを作成します。

作成したパターンに対象の文字列をマッチさせ、結果がNoneでなければ、その文字列はリスト内の要素の組み合わせで構成できると判断できます。

コード例

import re

chk_str = 'balloon'
Alist = ['fly','on', 'o', 'hot', 'ball', 'air']

def findstring(strchk, biglist):
    r = re.compile("(?:" + "|".join(biglist) + ")*$")
    if r.match(strchk) != None:
        return True
    return False

# 関数を使用
if(findstring(chk_str,Alist)):
    print("String can be formed.")
else:
    print("String can not be formed.")

実行結果

String can be formed.

このコードでは、(?:fly|on|o|hot|ball|air)*$という正規表現パターンを動的に生成しています。対象文字列全体がこれらの要素の繰り返しで構成されている場合にマッチするため、効率的に判定できます。

まとめ

リスト内の文字列を連結して目的の文字列が作成できるか判定するには、以下の2つのアプローチがあります。

• permutations方式： すべての組み合わせを網羅的に試すため確実ですが、リストの要素数が多いと計算量が急増します。
• 正規表現方式： パターンを1回コンパイルするだけで済むため、一般的により高速に動作します。

小規模なデータセットではどちらの方法でも問題ありませんが、パフォーマンスが重要な場合は正規表現方式の採用を検討するとよいでしょう。