在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