本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠。在這一系列刷題文章中，我不僅會講解多種解題思路及其優(yōu)化，還會用多種編程語言實現(xiàn)題解，涉及到通用解法時更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時可能發(fā)生更新變動，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

給出一個單詞數(shù)組?words?，其中每個單詞都由小寫英文字母組成。如果我們可以?不改變其他字符的順序?，在?wordA?的任何地方添加?恰好一個?字母使其變成?wordB?，那么我們認為?wordA?是?wordB?的?前身?。

• 例如，"abc"?是?"abac"?的?前身?，而?"cba"?不是?"bcad"?的?前身

詞鏈是單詞?[word_1, word_2, ..., word_k]?組成的序列，k >= 1，其中?word1?是?word2?的前身，word2?是?word3?的前身，依此類推。一個單詞通常是?k == 1?的?單詞鏈?。從給定單詞列表?words?中選擇單詞組成詞鏈，返回 詞鏈的?最長可能長度?。

示例 1：

輸入：words = ["a","b","ba","bca","bda","bdca"]
輸出：4
解釋：最長單詞鏈之一為 ["a","ba","bda","bdca"]

示例 2:

輸入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
輸出：5
解釋：所有的單詞都可以放入單詞鏈 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

示例?3:

輸入：words = ["abcd","dbqca"]
輸出：1
解釋：字鏈["abcd"]是最長的字鏈之一。
["abcd"，"dbqca"]不是一個有效的單詞鏈，因為字母的順序被改變了。

提示：

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

解法1 記憶化搜索+哈希表

對于字符串 $s$ 來說，假設(shè)它是詞鏈的最后一個單詞，那么去掉 $s$ 中的一個字母，設(shè)新字符串為 $t$ ，問題就變成計算以 $t$ 結(jié)尾的詞鏈的最長長度。由于這是一個和原問題相似的子問題，因此可以用遞歸解決。

直接把字符串作為遞歸的參數(shù)，定義 $dfs(s)$ 表示以 $s$ 結(jié)尾的詞鏈的最長長度。由于字符串的長度不超過 $16$ ，暴力枚舉去掉的字符，設(shè)新字符串為 $t$ 且在 $words$ 中，則有
dfs ( s ) = max ? { dfs ( t ) } + 1 \textit{dfs}(s) = \max\{\textit{dfs}(t)\} + 1 dfs(s)=max{dfs(t)}+1
為了快速判斷字符串是否在 $words$ 中，需要將所有 $\text{words}[i]$ 存入哈希表 $ws$ 中。

由于 "aba" 和 "aca" 去掉中間字母都會變成 "aa" ，為避免重復(fù)計算，代碼實現(xiàn)時可以用記憶化搜索。進一步地，可以直接把計算結(jié)果存到 $ws$ 中。（Python 可以使用 @cache ）

class Solution {
    private Map<String, Integer> ws = new HashMap<>();
    public int longestStrChain(String[] words) {
        for (var s : words) ws.put(s, 0); // 0表示未被計算
        int ans = 0;
        for (var s : ws.keySet())
            ans = Math.max(ans, dfs(s));
        return ans;
    }
    private int dfs(String s) { // dfs(s)表示以s為最后一個單詞的鏈的最長長度
        int res = ws.get(s);
        if (res > 0) return res; // 之前計算過
        for (int i = 0; i < s.length(); ++i) { // 枚舉去掉s[i] 
            var t = s.substring(0, i) + s.substring(i + 1);
            if (ws.containsKey(t)) // t在words中
                res = Math.max(res, dfs(t));
        }
        ws.put(s, res + 1); // 記憶化
        return res + 1;
    }
}

復(fù)雜度分析：

• 時間復(fù)雜度：$\mathcal{O}(n{L}^2)$ ，其中 $n$ 為 $words$ 的長度，$L$ 為字符串的最大長度，本題不超過 $16$ 。動態(tài)規(guī)劃的時間復(fù)雜度 = 狀態(tài)個數(shù) $\times$ 單個狀態(tài)的計算時間。這里狀態(tài)個數(shù)為 $\mathcal{O}(n)$ ，單個狀態(tài)的計算時間為 $\mathcal{O}(L^2)$，因此時間復(fù)雜度為 $\mathcal{O}(n{L}^2)$ 。
• 空間復(fù)雜度：$\mathcal{O}(nL)$ 。每個狀態(tài)都需要 $\mathcal{O}(L)$ 的空間。

解法2 動態(tài)規(guī)劃——1:1 翻譯成遞推

我們可以去掉遞歸中的「遞」，只保留「歸」的部分，即自底向上計算。對于本題，只需要把遞歸改成循環(huán)。由于總是從短的字符串轉(zhuǎn)移到長的字符串，所以要先把字符串按長度從小到大排序，然后從短的開始遞推。

class Solution {
    private Map<String, Integer> ws = new HashMap<>();
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        int ans = 0;
        for (var s : words) {
            int res = 0;
            for (int i = 0; i < s.length(); ++i) { // 枚舉去掉s[i]
                var t = s.substring(0, i) + s.substring(i + 1);
                res = Math.max(res, ws.getOrDefault(t, 0));
            }
            ws.put(s, res + 1);
            ans = Math.max(ans, res + 1);
        }
        return ans;
    }
}

復(fù)雜度分析：文章來源地址http://www.zghlxwxcb.cn/news/detail-447386.html

• 時間復(fù)雜度：$\mathcal{O}(n\log n+n{L}^2)$ ，其中 $n$ 為 $words$ 的長度，$L$ 為字符串的最大長度，本題不超過 $16$ 。排序的時間復(fù)雜度為 $\mathcal{O}(n\log n)$（注意只比較長度）。動態(tài)規(guī)劃的時間復(fù)雜度 = 狀態(tài)個數(shù) $\times$ 單個狀態(tài)的計算時間，這里狀態(tài)個數(shù)為 $\mathcal{O}(n)$ ，單個狀態(tài)的計算時間為 $\mathcal{O}(L^2)$ 。
• 空間復(fù)雜度：$\mathcal{O}(nL)$ 。每個狀態(tài)都需要 $\mathcal{O}(L)$ 的空間。

到了這里，關(guān)于LeetCode 1048. Longest String Chain【記憶化搜索,動態(tài)規(guī)劃,哈希表,字符串】中等的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！