四川建设网有限责 任公司网站宝安印刷网站建设

四川建设网有限责 任公司网站,宝安印刷网站建设,wordpress 标签云样式,彩票网站建设多少钱题目描述给定一组单词words#xff0c;编写一个程序#xff0c;找出其中的最长单词#xff0c;且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果#xff0c;返回其中字典序最小的一项#xff0c;若没有符合要求的单词则返回空字符串。示例#xff1a;输入…题目描述给定一组单词words编写一个程序找出其中的最长单词且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果返回其中字典序最小的一项若没有符合要求的单词则返回空字符串。示例输入[cat,banana,dog,nana,walk,walker,dogwalker]输出dogwalker解释dogwalker可由dog和walker组成。代码实现import java.util.*; class Solution { public String longestWord(String[] words) { // 按长度分组 MapInteger, ListString map new HashMap(); SetString set new HashSet(); int maxL 0; for (String s : words) { set.add(s); int k s.length(); map.computeIfAbsent(k, key - new ArrayList()).add(s); maxL Math.max(maxL, k); } // 从最长到最短检查 while (maxL 0) { if (map.containsKey(maxL)) { ListString list map.get(maxL); Collections.sort(list); // 字典序排序 for (String s : list) { set.remove(s); // 先移除当前单词 if (canBeFormed(s, set)) { return s; } set.add(s); // 恢复 } } maxL--; } return ; } private boolean canBeFormed(String word, SetString dict) { if (word.isEmpty()) return false; boolean[] dp new boolean[word.length() 1]; dp[0] true; for (int i 1; i word.length(); i) { for (int j 0; j i; j) { if (dp[j] dict.contains(word.substring(j, i))) { dp[i] true; break; } } } return dp[word.length()]; } }class Solution { public String longestWord(String[] words) { // 1. 对单词数组进行排序 // 规则优先按长度降序排列从长到短长度相同时按字典序升序排列 Arrays.sort(words, (o1, o2) - { if (o1.length() o2.length()) // 长度相同时按字典序升序排列a在前z在后 return o1.compareTo(o2); else { // 长度不同时按长度降序排列长在前短在后 return Integer.compare(o2.length(), o1.length()); } }); // 2. 创建HashSet存储所有单词便于快速查找 SetString set new HashSet(Arrays.asList(words)); // 3. 遍历排序后的单词数组 // 由于已经按长度降序、字典序升序排序找到的第一个符合条件的单词就是答案 for (String word : words) { // 3.1 先将当前单词从集合中移除确保不会使用单词本身来构造自己 set.remove(word); // 3.2 检查当前单词是否能由集合中的其他单词组成 if (find(set, word)) return word; // 找到符合条件的单词直接返回 // 3.3 恢复集合准备检查下一个单词 set.add(word); } // 4. 没有找到符合条件的单词返回空字符串 return ; } // 递归方法判断给定的单词是否能由字典set中的单词组成 public boolean find(SetString set, String word) { // 基线条件如果单词长度为0说明已经成功匹配完成 if (word.length() 0) return true; // 尝试所有可能的分割点 for (int i 0; i word.length(); i) { // 将单词分为两部分word[0...i] 和 word[i1...end] String prefix word.substring(0, i 1); // 如果前缀存在于字典中并且剩余部分也能由字典中的单词组成 if (set.contains(prefix) find(set, word.substring(i 1))) return true; // 找到一种有效的分割方式 } // 所有分割方式都尝试过了无法组成该单词 return false; } }