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

如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。

  • 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。

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

示例 1：

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

示例 2:

输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出：5
解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

示例 3:

输入：words = ["abcd","dbqca"]
输出：1
解释：字链["abcd"]是最长的字链之一。
["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。

 

提示：

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 16
  • words[i] 仅由小写英文字母组成。
Related Topics
  • 数组
  • 哈希表
  • 双指针
  • 字符串
  • 动态规划

  • 👍 167
  • 👎 0

    • 凑合还行，java，我也不知道叫啥了，试试使用并发类？

    勉强97.26%

    双指针判断前身字符串，
    哈希表把字符串按长度整理好
    当前字符串和长度加1的字符串集合对比，
    然后从最短的一组开始尝试作为起始点，每次取到最长长度后取最大值

    代码

    class Solution {
    public int longestStrChain(String[] words) {
        HashMap<Integer, List<String>> hashMap = new HashMap<>();

        int minLength = 1000;
        int maxLength = 0;
        for (String word : words) {
            minLength = Math.min(minLength,word.length());
            maxLength = Math.max(maxLength,word.length());
            if (!hashMap.containsKey(word.length())){
                hashMap.put(word.length(),new ArrayList<>());
            }
            hashMap.get(word.length()).add(word);
        }
        int res = 1;
        for (int currentLength = minLength; res+currentLength <= maxLength; currentLength++) {
            int l = currentLength;
            int chainL = 1;
            List<String> stringList = hashMap.get(l);
            HashSet<String> nextStrings = new HashSet<>();
            l++;

            while (hashMap.containsKey(l)){
                List<String> nextList = hashMap.get(l);
                for (String str1 : stringList) {
                    for (String str2 : nextList) {
                        if (isBefore(str1,str2)){
                            nextStrings.add(str2);
                        }
                    }
                }
                if (nextStrings.size()>0){
                    chainL++;
                }else{
                    break;
                }
                l++;
                stringList = new ArrayList<>(nextStrings);
                nextStrings.clear();
            }
            res = Math.max(chainL,res);
        }

        return res;
    }

    /**
     * 双指针
     */
    private boolean isBefore(String str1, String str2){
        int idx1 = 0;
        int idx2 = 0;
        //头对齐
        if (str1.charAt(0)!= str2.charAt(0)){
            idx2 = 1;
        }
        while (idx1 < str1.length() && idx2< str2.length()){
            while (idx2< str2.length() && str1.charAt(idx1) != str2.charAt(idx2)){
                idx2++;
            }
            if (idx2< str2.length() && str1.charAt(idx1) == str2.charAt(idx2)){
                idx2++;
                idx1++;
            }
        }
        return idx1 == str1.length();
    }
}

    以及一些碎碎念

    当res+currentLength <= maxLength的时候，如果不停止的话，后面算到的res值只会越来越小
    如果用currentLength < maxLength判断的话就会变成击败5%了

    当然还有个地方能优化

    if (isBefore(str1,str2)){
    nextStrings.add(str2);
    hashMap.get(l).remove(str2);
}

    算过的字符串就完全可以删掉了以后不用再算了，可以删除掉
    但是会引发

    java.util.ConcurrentModificationException

    所以原来哈希表要换成

    HashMap<Integer, CopyOnWriteArrayList<String>> hashMap

    不过好像没啥提升，看起来这边的瓶颈不在这里
    但是删掉处理过的字符串之后即使是用 currentLength < maxLength 也能击败94%了