難度：★★★☆☆
類型：字符串
方法：動(dòng)態(tài)規(guī)劃

題目

力扣鏈接請(qǐng)移步本題傳送門
更多力扣中等題的解決方案請(qǐng)移步力扣中等題目錄

給出一個(gè)單詞列表，其中每個(gè)單詞都由小寫英文字母組成。

如果我們可以在 word1 的任何地方添加一個(gè)字母使其變成 word2，那么我們認(rèn)為 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。

詞鏈?zhǔn)菃卧~ [word_1, word_2, ..., word_k] 組成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此類推。

從給定單詞列表 words 中選擇單詞組成詞鏈，返回詞鏈的最長(zhǎng)可能長(zhǎng)度。

示例：

輸入：["a","b","ba","bca","bda","bdca"]
輸出：4
解釋：最長(zhǎng)單詞鏈之一為 "a","ba","bda","bdca"。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] 僅由小寫英文字母組成。

解答

單詞是以集合的形式給出的，這也就意味著，是無序的，這是這道題目需要注意的一點(diǎn)。

我們使單詞按照長(zhǎng)度從短到長(zhǎng)排序，便于動(dòng)態(tài)規(guī)劃的遍歷統(tǒng)計(jì)。

【數(shù)組定義】

定義字典dp，字典中的鍵代表每個(gè)單詞word，字典的值代表以單詞word結(jié)尾的鏈的最大長(zhǎng)度。

【初始狀態(tài)】

將每個(gè)單詞對(duì)應(yīng)的數(shù)值填充為零。

【遞推公式】

從短到長(zhǎng)遍歷每個(gè)單詞word，研究該單詞分別去掉其中一個(gè)字符后形成的單詞word_strip，查看它是否在單詞列表中出現(xiàn)過，若該單詞出現(xiàn)在列表中，則說明可以將word_strip結(jié)尾的鏈增加一個(gè)word延長(zhǎng)一個(gè)長(zhǎng)度，dp[word_strip] + 1（當(dāng)然需要和當(dāng)前值dp[word]進(jìn)行比較，選更大的），如果word去掉每個(gè)位置處的字母得到的新單詞都沒有出現(xiàn)在單詞列表words中，則dp[word]設(shè)置為1。

【返回值】

最終返回dp字典的值列表中的最大值即可。

from typing import List
from collections import defaultdict
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        dp = defaultdict(int)
        words.sort(key=len)
        for word in words:
            for i in range(len(word)):
                word_strip = word[:i] + word[i + 1:]
                dp[word] = max(dp[word], dp[word_strip] + 1)
        return max(dp.values())

擴(kuò)展：如果有順序要求呢

如果單詞不是以集合的形式給出，而是以列表的形式給出，也就是說需要保證有序，那么這道題就轉(zhuǎn)換成了類似300.求最長(zhǎng)遞增子序列的問題。也是要用動(dòng)態(tài)規(guī)劃。換了一個(gè)馬夾而已，請(qǐng)看原來題目的解法：

from typing import List
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        dp = [1 for _ in range(n)]
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j] + 1)
        return max(dp)

對(duì)于這道題，重新增加一個(gè)函數(shù)用來比較單詞之間能否建立連接就好了。

class Solution:
    def longestStrChain(self, words: List[str]) -> int:

        if not words:
            return 0
        n = len(words)
        dp = [1 for _ in range(n)]
        words.sort(key=len)                         # 如果要求順序，則不需要這句話
        for i in range(n):
            for j in range(i):
                if self.cmp(words[j], words[i]):
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

    @staticmethod
    def cmp(w1, w2):
        if len(w1) + 1 != len(w2):
            return False
        w1, w2 = list(w1), list(w2)
        while w1 and w1[0] == w2[0]:
            w1.pop(0)
            w2.pop(0)
        w2.pop(0)
        while w1 and w1[0] == w2[0]:
            w1.pop(0)
            w2.pop(0)
        if w1 == w2 == []:
            return True
        return False

這里可以通過 words.sort(key=len) 這句話的有無來控制題目是否要求有序。讀者把這段代碼粘貼過去也是可以運(yùn)行的。

如有疑問或建議，歡迎評(píng)論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請(qǐng)移步力扣中等題解析