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

假设我们有一个名为 w 的单词列表，带有小写字符串。我们必须找到 w 的最长序列的长度，其中每个前一个词是下一个词的前缀，下一个词只附加一个新字符。

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

示例

让我们看看以下实现以获得更好的理解 -

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