用 Python 编写程序，查找单词数组中最长前缀序列的长度

pythonserver side programmingprogramming更新于 2026/1/23 11:56:17

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

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

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

对列表 w 进行排序
dp := 一个映射，其中键的默认值为 0
res := 0
对 w 中的每个单词执行
- dp[word] := dp[单词子字符串到倒数第二个元素] + 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))