Python程序：查找由给定字母组成的最长单词的长度

假设我们有一系列单词和一个名为letters的字符串，我们需要找到通过重新排列给定字母可以组成的最长单词的长度。在letters中可能包含星号字符(*)，它可以匹配任何字符。并且不需要使用所有字母。

因此，如果输入类似于words = ["prince", "rice", "price", "limit", "hello"] letters = "*r**ce*"，则输出将为6，因为我们可以组成的最长单词是“prince”，长度为6。

为了解决这个问题，我们将遵循以下步骤

  • has := 一个包含letters中每个元素的字母和频率的映射
  • 定义一个函数valid()。它将接收s
  • need := 一个包含s中每个元素的字母和频率的映射
  • extra := (对于need中的所有字符，计算need[char] - has[char] 的最大值（0和need[char] - has[char]中的较大值）之和
  • 当extra <= has["*"]时返回true
  • 从主方法执行以下操作
  • 返回列表中所有元素的最大值：[当单词有效时，所有单词中单词的长度]

让我们看看以下实现，以便更好地理解

示例

在线演示

from collections import Counter

class Solution:
   def solve(self, words, letters):
      has = Counter(letters)

      def valid(s):
         need = Counter(s)
         extra = sum([max(0, need[char] - has[char]) for char in need])
         return extra <= has["*"]

      return max([len(word) for word in words if valid(word)])

ob = Solution()
words = ["prince", "rice", "price", "limit", "hello"]
letters = "*r**ce*"
print(ob.solve(words, letters))

输入

["prince", "rice", "price", "limit", "hello"], "*r**ce*"

输出

6

更新于: 2020年11月26日

254 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告