Pythonで指定された文字から形成できる最長の単語の長さを見つけるプログラム

単語のリストと文字と呼ばれる文字列があるとすると、指定された文字を並べ替えることで作成できる最長の単語のサイズを見つける必要があります。文字にはアスタリスク文字（*）が含まれている場合があり、任意の文字と一致する可能性があります。また、すべての文字を使用する必要はありません。

したがって、入力がwords =["prince"、 "rice"、 "price"、 "limit"、 "hello"] Letters ="* r ** ce *"の場合、出力は6になります。私たちが作ることができる最長の単語は「王子」です。長さは6です。

これを解決するには、次の手順に従います。

• has：=文字と文字の各要素の頻度を含むマップ
• 関数valid（）を定義します。これには時間がかかります
• need：=sの各要素の文字と頻度を含むマップ
• extra：=のすべての要素の合計（最大0およびneed [char]-必要なすべてのcharに対してhas[char]）
• 余分な<=has["*"]
の場合は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