网站建设开发 脚本语言,做公众号模板的网站,代驾系统定制开发,wordpress建企业门户给出一个单词数组 words #xff0c;其中每个单词都由小写英文字母组成。
如果我们可以 不改变其他字符的顺序 #xff0c;在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB #xff0c;那么我们认为 wordA 是 wordB 的 前身 。
例如#xff0c;“abc” 是 “abac”…给出一个单词数组 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));MapString, 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, max1);}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[i1:]if v,ok:mapx[s];ok {max getMax(max, v)}}mapx[word] max 1res getMax(res, max1)}return res
}func getMax(x,y int) int{if xy {return x}return y
}
