【Leetcode】1048. Longest String Chain

題目位址：

https://leetcode.com/problems/longest-string-chain/

給定一個單詞清單 A A A，如果一個單詞 s 1 s_1 s1​在任意位置添加 a ∼ z a \sim z a∼z的一個字元成為了 s 2 s_2 s2​，就可以将 s 2 s_2 s2​接到 s 1 s_1 s1​後面形成一條鍊。求該單詞清單中的最長鍊長度。題目保證所有單詞隻含小寫字母。

記憶化搜尋的寫法可以參照https://blog.csdn.net/qq_46105170/article/details/108688092。下面介紹動态規劃遞推的方法。

先将字元串按照長度排序，這樣就能保證每個字元串的前驅一定在其前面。接着開始遞推，設 f [ i ] f[i] f[i]表示以 A [ i ] A[i] A[i]結尾的最長鍊的長度。接着枚舉鍊的倒數第二個字元串，如果将 A [ i ] A[i] A[i]删去一個字母後得到的字元串如果前面出現過，比如說其下标是 j j j（由于長度短的排在前面，是以可以保證 A [ j ] A[j] A[j]結尾的最長鍊一定被算出來了），那就可以将其的最長連結到 A [ i ] A[i] A[i]前面，進而 f [ i ] f[i] f[i]可以更新為 f [ j ] + 1 f[j]+1 f[j]+1。一路遞推下去同時記錄 f f f的最大值即可。上面我們可以發現，需要查詢某個字元串出現的下标，這可以用Trie當做哈希表來存這個資訊（直接用HashMap也可以，碰撞的機率并不高）。看出代碼如下：

import java.util.Arrays;

public class Solution {
    
    class Trie {
        class Node {
            Node[] nexts;
            boolean isWord;
            int idx;
    
            public Node() {
                nexts = new Node[26];
            }
        }
        
        private Node root;
    
        public Trie() {
            root = new Node();
        }
    
        public void put(String word, int idx) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (cur.nexts[ch - 'a'] == null) {
                    cur.nexts[ch - 'a'] = new Node();
                }
                
                cur = cur.nexts[ch - 'a'];
            }
            
            cur.isWord = true;
            cur.idx = idx;
        }
        
        public int get(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (cur.nexts[ch - 'a'] == null) {
                    return -1;
                }
                
                cur = cur.nexts[ch - 'a'];
            }
            
            return cur.isWord ? cur.idx : -1;
        }
    }
    
    public int longestStrChain(String[] words) {
    	// 先按長度排序
        Arrays.sort(words, (w1, w2) -> Integer.compare(w1.length(), w2.length()));
        int[] dp = new int[words.length];
        
        Trie mapToIdx = new Trie();
        // 存一下每個字元串出現的下标
        for (int i = 0; i < words.length; i++) {
            mapToIdx.put(words[i], i);
        }
        
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            dp[i] = 1;
            String word = words[i];
            // 枚舉删去word[j]
            for (int j = 0; j < word.length(); j++) {
                String pre = word.substring(0, j) + word.substring(j + 1);
                int idx = mapToIdx.get(pre);
                // 能找到就更新dp[i]
                if (idx != -1) {
                    dp[i] = Math.max(dp[i], 1 + dp[idx]);
                }
                
            }
            
            // 更新全局最優解
            res = Math.max(res, dp[i]);
        }
        
        return res;
    }
}
           

時間複雜度 O ( n l log ⁡ n ) O(nl\log n) O(nllogn)，空間 O ( n l ) O(nl) O(nl)。