Python 中查詢最短的完整單詞

假設我們有一個字典 words，我們需要從給定的字典 words 中找到最小長度的單詞，它包含字串 licensePlate 中的所有字母。現在，這樣的單詞被稱為完整給定字串 licensePlate。這裡，我們將忽略字母的大小寫。並且保證存在答案。如果有多個答案，則返回陣列中第一個出現的答案。

車牌號中可能存在相同的字母出現多次。因此，當 licensePlate 為 "PP" 時，單詞 "pile" 無法完整匹配 licensePlate，但單詞 "topper" 可以。

因此，如果輸入類似 licensePlate = "1s3 PSt"，words = ["step", "steps", "stripe", "stepple"]，則輸出將為 "steps"，因為包含字母 "S"、"P"、"S"、"T" 的最小長度單詞。

為了解決這個問題，我們將遵循以下步驟：

• alphabet := "abcdefghijklmnopqrstuvwxyz"
• letters := 透過獲取 licensePlate 中所有屬於 alphabet 的字元 s 並將其轉換為小寫，得到一個列表。
• valid_words := 一個新的列表。
• 對於 words 中的每個 i：
  • append := True
  • 對於 letters 中的每個 j：
    • append := append 並且 (letters 中 j 的數量 <= i 中 j 的數量)
  • 如果 append 為真，則
    • 將 i 插入到 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"]))

輸入

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

輸出

steps

Arnab Chakraborty

更新於: 2020年7月4日

288 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習