LEETCODE 1048. 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 中选择单词组成词链，返回词链的最长可能长度。

示例：

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

提示：

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1048

解题思路分析：

如果想组成链，必须找到一个比当前字符串长度小一的字符串，没有的话，以当前字符为结尾的链长最大只能为1。基于这个思路，

1. 我们先建立一个Map lengthMap，用于存储每种长度的字符串有哪些。
2. 接下来，再新建一个Map，用来存储以每个字符串为结尾的最长链的长度。
3. 然后，从长度为1的字符串开始循环，如果不存在当前字符串长度减一的字符串，那么当前字符串能组成的最大长度为1，将结果保存至map中。如果存在的话，则需要将当前字符串分别按顺序剔除掉一个字符，形成一个子字符串序列，并查看该子序列是否存在于map中，如果存在，该子序列在map中的值再加一即为当前字符串能够组成的一条链的长度，遍历完该字符串所有子序列之后，其中最大值即为以该字符串结尾的最大链长。
4. 遍历完所有字符串之后，自然也就得到最大链长是多少。

本解法时间复杂度为O(n*m)，n为数组个数，m为字符串长度。看下完整代码。

public int longestStrChain(String[] words) {
    // 将字符串按照长度分组，并存处于lengthMap 中
    Map<Integer, List<String>> lengthMap = new HashMap<>();
    int maxlength=0;
    for(String word : words){
        int length = word.length();
        List<String> list = lengthMap.getOrDefault(length, new ArrayList<>());
        list.add(word);
        lengthMap.put(length, list);
        maxlength = Math.max(maxlength, length);
    }
    // map的key为每个字符串，value为以该字符串结尾的最大链长
    Map<String, Integer> map = new HashMap<>();
    int res = 1; // 返回结果
    for(int i=1;i<=maxlength;i++){
        if(!lengthMap.containsKey(i)){ // 如果不存在长度为i的字符串，跳过
            continue;
        }
        List<String> list = lengthMap.get(i); // 取得长度为i的字符串列表
        for(String s : list){ // 循环长度为i的字符串
            // 如果不存在长度为i-1的字符串
            if(!lengthMap.containsKey(i-1)){
                map.put(s, 1); // 将当前字符串的链长设置为1
            }else{
                int count = 1;
                for(int j=0;j<i;j++){ // 将当前字符串减掉一个字符
                    String pre = s.substring(0,j)+s.substring(j+1);
                    if(map.containsKey(pre)){ // 如果map中存在该序列
                        // 更新以当前字符串结尾的最大链长
                        count = Math.max(count, map.get(pre)+1);
                    }
                }
                map.put(s, count); // 保存以当前字符串结尾的最大链长
                res = Math.max(count, res); // 更新返回结果最大值
            }
        }
    }
    return res;
}

本题解法运行时间为20ms。

Runtime: 20 ms, faster than 94.85% of Java online submissions for Longest String Chain.

Memory Usage: 37.9 MB, less than 100.00% of Java online submissions for Longest String Chain.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1048-longest-string-chain-解题思路分析/