Python 中最短的补全单词
pythonserver side programmingprogramming更新于 2023/11/9 22:26:00
假设我们有一个字典 words，我们必须从给定的字典 words 中找出长度最小的单词，它包含字符串 licensePlate 中的所有字母。现在，这样的单词被称为补全给定的字符串 licensePlate。在这里，我们将忽略字母的大小写。并且保证存在一个答案。如果有多个答案，则返回数组中第一个出现的答案。
车牌上可能会出现多次相同的字母。因此，当车牌为"PP"时，单词"pile"不会补全车牌，但单词"topper"会补全车牌确实如此。
因此，如果输入类似于 licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]，则输出将为 "steps"，因为包含字母的最小长度单词是 "S", "P", "S", "T"。
为了解决这个问题，我们将遵循以下步骤 −
- alphabet := "abcdefghijklmnopqrstuvwxyz"
- letters := 一个小写的 s 列表，当 s 是字母表时，从 licensePlate 中取出所有 s
- valid_words := 一个新的列表
- 对于单词中的每个 i，执行
- append := True
- 对于字母中的每个 j，执行
- append := append 并且 (字母中的 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
