Pythonで最短の単語を完成させる

辞書の単語があり、与えられた辞書の単語から最小の長さの単語を見つけなければならないと仮定すると、文字列licensePlateからのすべての文字が含まれます。今、そのような単語は与えられた文字列licensePlateを完了すると言われています。ここでは、文字の大文字小文字を無視します。そして、答えが存在することが保証されています。複数の回答がある場合は、配列の最初に発生する回答を返します。

ナンバープレートには、同じ文字が複数回出現する場合があります。したがって、「PP」のlicensePlateの場合、「pile」という単語はlicensePlateを完成させませんが、「topper」という単語は完成します。

したがって、入力がlicensePlate ="1s3 PSt"、words =["step"、 "steps"、 "stripe"、 "stepple"]の場合、出力は「steps」になります。文字は「S」、「P」、「S」、「T」です。

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

• アルファベット：="abcdefghijklmnopqrstuvwxyz"
• 文字：=sがアルファベットの場合、licensePlateからすべてのsを取得することによる小文字のsのリスト
• valid_words：=新しいリスト
• 単語のiごとに、
  • add：=True
  • 文字のjごとに、
    • append：=append and（文字内のjの数<=i内のjの数）
  • appendがtrueの場合、
    • valid_wordsの最後にiを挿入
• 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"]))

入力

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

出力

steps