Pythonでライセンスプレートを完成させる最短単語を見つける方法

問題概要

単語のリスト words が与えられたとき、文字列 licensePlate に含まれるすべての文字を持つ、リスト内で最も短い単語を見つけます。このような単語は、指定された licensePlate を「完成させる（complete）」単語と呼ばれます。ここでは大文字と小文字は区別せず、必ず答えが存在することが保証されています。また、条件を満たす単語が複数ある場合は、配列の中で最初に出現するものを返します。

ナンバープレートには、同じ文字が複数回出現する場合があります。たとえば licensePlate が「PP」である場合、単語「pile」は P が1つしかないためプレートを完成させられませんが、「topper」は P を2つ持っているため完成させることができます。

例として、入力が licensePlate = "1s3 PSt"、words = ["step", "steps", "stripe", "stepple"] の場合を考えてみましょう。このとき出力は「steps」になります。「S」「P」「S」「T」という文字をすべて含む最短の単語が「steps」だからです。

解決のための手順

この問題を解くには、以下の手順に従います。

• alphabet に「abcdefghijklmnopqrstuvwxyz」を設定します。
• licensePlate からアルファベットのみを抽出し、小文字に変換したリスト letters を作成します。
• 空のリスト valid_words を用意します。
• words 内の各単語 i について、以下を繰り返します。
  • フラグ append を True で初期化します。
  • letters 内の各文字 j について、「letters における j の出現回数 ≤ 単語 i における j の出現回数」が成り立つかを確認し、結果を append に反映します。
  • append が True のままの場合、その単語を valid_words の末尾に追加します。
• valid_words の中から最も長さの短い単語を返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
   def shortestCompletingWord(self, licensePlate, words):
      alphabet = "abcdefghijklmnopqrstuvwxyz"
      letters = [s.lower() for s in licensePlate if s.lower() in alphabet]
      valid_words = []
      for i in words:
         append = True
         for j in letters:
            append = append and (letters.count(j) <= i.count(j))
         if append:
            valid_words.append(i)
      return min(valid_words, key=len)
ob = Solution()
print(ob.shortestCompletingWord("1s3 PSt", ["step", "steps",
"stripe", "stepple"]))

コードの解説

まず、リスト内包表記を使って licensePlate から数字や記号などの不要な文字を取り除き、残った文字をすべて小文字に変換して letters リストを作成しています。次に、各単語に対して count() メソッドを用い、letters に含まれる各文字が必要な回数だけその単語にも含まれているかを確認します。この条件を満たす単語だけを valid_words に集め、最後に min(valid_words, key=len) によって最も短い単語を取得しています。min() は条件を満たす単語のうち最初のものを返すため、「複数の候補がある場合は先頭の要素を返す」という要件も自然に満たされます。

入力

"1s3 PSt", ["step", "steps", "stripe", "stepple"]

出力

steps