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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-string-chain
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

记忆化搜索

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

    private Map<Integer, List<String>> dictList;

    private Map<String, Integer> dp = new HashMap<>();

    private boolean isNext(String w1, String w2) {
        if (w1.length() + 1 != w2.length()) {
            return false;
        }
        int index1 = 0, index2 = 0;
        while (index1 < w1.length() && index2 < w2.length() && w1.charAt(index1) == w2.charAt(index2)) {
            index1++;
            index2++;
        }
        /**
         * 在末尾添加
         */
        if (index1 == w1.length()) {
            return true;
        }

        index2++;
        while (index1 < w1.length() && index2 < w2.length() && w1.charAt(index1) == w2.charAt(index2)) {
            index1++;
            index2++;
        }
        return index1 == w1.length();
    }

    private int solve(String word) {
        if (!dp.containsKey(word)) {
            int nextLength = word.length() + 1;
            List<String> list = dictList.get(nextLength);
            if (list == null) {
                dp.put(word, 1);
            } else {
                int ans = 0;
                for (String item : list) {
                    if (isNext(word, item)) {
                        ans = Math.max(ans, solve(item));
                    }
                }
                dp.put(word, ans + 1);
            }
        }
        return dp.get(word);
    }

    public int longestStrChain(String[] words) {
        if (words == null || words.length == 0) {
            return 0;
        }

        int minLength = Integer.MAX_VALUE;
        int maxLength = Integer.MIN_VALUE;

        Map<Integer, List<String>> dictList = new HashMap<>();
        for (String word : words) {
            dictList.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);
            minLength = Math.min(minLength, word.length());
            maxLength = Math.max(maxLength, word.length());
        }
        this.dictList = dictList;
        int ans = 0;

        for (String word : words) {
            ans = Math.max(ans, solve(word));
        }

        return ans;
    }
}

排序 + 动态规划

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

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