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

更新于: 2020年7月4日

288 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告