Pythonで指定した文字から作れる最長の単語の長さを求めるプログラム(ワイルドカード対応)

単語のリスト words と文字列 letters が与えられたとき、letters に含まれる文字を並べ替えて作ることができる「最長の単語」の長さを求める問題を考えてみましょう。

この問題には2つのポイントがあります。

• letters にはアスタリスク(*)が含まれることがあり、これは任意の1文字として扱えるワイルドカードです。
• 与えられた文字をすべて使い切る必要はありません。

たとえば、入力が次のような場合を考えます。

words = ["prince", "rice", "price", "limit", "hello"]
letters = "*r**ce*"

このとき出力は 6 になります。ワイルドカードのおかげで最も長い単語 "prince"(長さ6)を作れるためです。

解き方のアプローチ

この問題は、各単語が与えられた文字で構成できるかどうかを判定し、条件を満たす単語の中で最大の長さを返すことで解けます。手順は以下の通りです。

• has:letters 内の各文字とその出現回数を格納するマップ(Counter)を作成します。
• 関数 valid() を定義します。引数として判定対象の文字列 s を受け取ります。
• need:s 内の各文字とその出現回数を格納するマップを作成します。
• extra:need 内の各文字について max(0, need[char] - has[char])(= 文字が足りない分)を計算し、その合計を求めます。
• extra <= has["*"] であれば、不足分をワイルドカードで補えるので True を返します。
• メイン処理では、words のうち valid() が True となる単語の長さの最大値を返します。

実装例

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

from collections import Counter

class Solution:
    def solve(self, words, letters):
        has = Counter(letters)

        def valid(s):
            need = Counter(s)
            extra = sum([max(0, need[char] - has[char]) for char in need])
            return extra <= has["*"]

        return max([len(word) for word in words if valid(word)])

ob = Solution()
words = ["prince", "rice", "price", "limit", "hello"]
letters = "*r**ce*"
print(ob.solve(words, letters))

入力

["prince", "rice", "price", "limit", "hello"], "*r**ce*"

出力

6

コードのポイント

この実装で重要なのは、Python標準ライブラリの collections.Counter を使っている点です。Counter を使うことで、文字列内の各文字の出現回数を1行で簡単に集計できます。

また、valid() 関数内のロジックが巧妙です。単語に必要な文字が letters に足りているかを確認し、足りない文字数の合計(extra)がワイルドカード * の個数以下であれば、その単語は作成可能と判断します。これにより、ワイルドカードを柔軟に活用できます。

計算量は、単語の数を N、各単語の平均的な長さを L とすると、おおよそ O(N × L) となり、非常に効率的です。