Python程序：查找单词数组中最长前缀序列的长度

假设我们有一个包含小写字符串的单词列表w。我们需要找到w中最长序列的长度，其中每个前一个单词都是下一个单词的前缀，而下一个单词仅附加一个新字符。

例如，如果输入为w = ["pqr", "pq", "m", "mn", "pqrs"]，则输出将为3，因为我们可以得到序列：["pq", "pqr", "pqrs"]，其长度为3。

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

• 对列表w进行排序
• dp := 一个映射，其中键的默认值为0
• res := 0
• 对于w中的每个单词，执行以下操作：
  • dp[word] := dp[word的倒数第二个字符之前的子串] + 1
  • res := res和dp[word]中的最大值
• 返回res

示例

让我们看下面的实现来更好地理解：

from collections import defaultdict
def solve(w):
   w.sort()
   dp = defaultdict(int)
   res = 0
   for word in w:
      dp[word] = dp[word[:-1]] + 1
      res = max(res, dp[word])
   return res

w = ["pqr", "pq", "m", "mn", "pqrs"]
print(solve(w))

输入

["pqr", "pq", "m", "mn", "pqrs"]

输出

3

Arnab Chakraborty

更新于：2021年10月19日

浏览量：189

启动您的职业生涯

完成课程获得认证

开始学习