【Java|golang】1048. 最长字符串链

给出一个单词数组 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] 仅由小写英文字母组成。

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

func longestStrChain(words []string) int {sort.Slice(words, func(i, j int) bool {return len(words[i])<len(words[j])})mapx:=make(map[string]int,0)res := 0for _, word := range words {max := 0for i := 0; i < len(word); i++ {s:=word[0:i]+word[i+1:]if v,ok:=mapx[s];ok {max = getMax(max, v)}}mapx[word]= max + 1res = getMax(res, max+1)}return res
}func getMax(x,y int) int{if x>y {return x}return y
}