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

啟動您的職業生涯

完成課程獲得認證

開始學習