目录链接:
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目:
https://github.com/September26/java-algorithms
原题链接:力扣
描述:
给出一个单词数组 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]
仅由小写英文字母组成。
解题思路:
* 解题思路: * 构建一个Map<Integer, Map<String, Integer>>类型的map,key代表字符串长度,value的Map代表每个字符串的单词链最长长度。 * 然后按照单词的长度分组。 * 分别遍历单词的长度length分别遍历,每次遍历时,去查找length-1长度的map中,是否有满足要求的,如果有,则在其长度上+1,如果没有,则长度设置为1。
代码:
public class Solution1048 {int mMax = 1;public int longestStrChain(String[] words) {Arrays.sort(words, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return o1.length() - o2.length();}});TreeMap<Integer, List<String>> tree = new TreeMap<>();for (String str : words) {int length = str.length();List<String> strings = tree.get(length);if (strings == null) {strings = new ArrayList<>();tree.put(length, strings);}strings.add(str);}Map<Integer, Map<String, Integer>> map = new HashMap<>();for (int i = 0; i <= 16; i++) {map.put(i, new HashMap<>());}for (int length : tree.keySet()) {List<String> strings = tree.get(length);search(length, strings, map);}return mMax;}public void search(int length, List<String> list, Map<Integer, Map<String, Integer>> map) {Map<String, Integer> shortMap = map.get(length - 1);Map<String, Integer> longMap = map.get(length);for (String str : list) {for (String key : shortMap.keySet()) {if (isMatch(key, str)) {int newLength = shortMap.get(key) + 1;longMap.put(str, Math.max(newLength, longMap.getOrDefault(str, 0)));mMax = Math.max(mMax, newLength);}}if (longMap.get(str) == null) {longMap.put(str, 1);}}}public boolean isMatch(String shortStr, String longStr) {if ((longStr.length() - shortStr.length()) != 1) {return false;}char[] chars1 = shortStr.toCharArray();char[] chars2 = longStr.toCharArray();int num = 0;for (int i = 0; i < chars2.length; i++) {if (i - num == chars1.length) {return true;}if (chars1[i - num] == chars2[i]) {continue;}num++;if (num > 1) {return false;}}return true;}
}