题目链接

英文链接：https://leetcode.com/problems/longest-string-chain/

中文链接：https://leetcode-cn.com/problems/longest-string-chain/

题目详述

给出一个单词列表，其中每个单词都由小写英文字母组成。

如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，”abc” 是 “abac” 的前身。

词链是单词 [word_1, word_2, …, word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。

从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。

示例：

1
2
3

输入：["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 "a","ba","bda","bdca"。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] 仅由小写英文字母组成。

题目详解

首先把字符串按照长度从小到大排序。
用 f[i] 表示到当前字符串组成的词链的最大长度。
遍历字符串，判断当前字符串能否由它前面的字符串添加一个字母得到。如果可以，更新当前结果，即 f[i] = Math.max(f[i], f[j] + 1);。
最终的结果为 f[i] 的最大值。
时间复杂度为 O(n^2L)，其中 n 为字符串数量，L 为字符串长度。

public class LeetCode_01048 {

    public int longestStrChain(String[] words) {
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return Integer.compare(o1.length(), o2.length());
            }
        });
        int n = words.length;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (check(words[j], words[i])) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }
        int res = 0;
        for (int x : f) {
            res = Math.max(res, x);
        }
        return res;
    }

    private boolean check(String s, String t) {
        if (s.length() + 1 != t.length()) {
            return false;
        }
        int[] map = new int[26];
        for (char c : t.toCharArray()) {
            ++map[c - 'a'];
        }
        for (char c : s.toCharArray()) {
            if (--map[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

可以对上面的解法做一点改进。
同样首先把字符串按照长度从小到大排序。
用 Map<String, Integer> map 表示到当前字符串组成的词链的最大长度。
遍历字符串，删掉当前字符串的一个字符得到一个新的字符串，判断这个字符串是否在之前出现过。如果是，更新当前结果。
排序花费时间为 O(nlogn)，遍历花费时间为 O(nL)，时间复杂度为两者较大值，其中 n 为字符串数量，L 为字符串长度。

public class LeetCode_01048 {

    public int longestStrChain(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        int res = 0;
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            int x = 1;
            for (int i = 0; i < word.length(); ++i) {
                String pre = word.substring(0, i) + word.substring(i + 1);
                x = Math.max(x, map.getOrDefault(pre, 0) + 1);
            }
            map.put(word, x);
            res = Math.max(res, x);
        }
        return res;
    }
}