【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)。