Java实现 LeetCode 472 连接词
2023-09-14 08:58:04 时间
472. 连接词
给定一个不含重复单词的列表,编写一个程序,返回给定单词列表中所有的连接词。
连接词的定义为:一个字符串完全是由至少两个给定数组中的单词组成的。
示例:
输入: [“cat”,“cats”,“catsdogcats”,“dog”,“dogcatsdog”,“hippopotamuses”,“rat”,“ratcatdogcat”]
输出: [“catsdogcats”,“dogcatsdog”,“ratcatdogcat”]
解释: “catsdogcats"由"cats”, “dog” 和 "cats"组成;
“dogcatsdog"由"dog”, "cats"和"dog"组成;
“ratcatdogcat"由"rat”, “cat”, "dog"和"cat"组成。
说明:
给定数组的元素总数不超过 10000。
给定数组中元素的长度总和不超过 600000。
所有输入字符串只包含小写字母。
不需要考虑答案输出的顺序。
class Solution {
private Set<String> wordSet;
public List<String> findAllConcatenatedWordsInADict(String[] words) {
wordSet = new HashSet<>();
for (String word : words) {
wordSet.add(word);
}
List<String> result = new ArrayList<String>();
Arrays.asList(words).parallelStream().forEach(word -> {
if (dfs(word, 0, 0, new StringBuilder())) {
result.add(word);
}
});
return result;
}
private boolean dfs(String word, int count, int start, StringBuilder sb) {
for (int i = start; i < word.length(); i++) {
sb.append(word.charAt(i));
boolean isWord = wordSet.contains(sb.toString());
if (isWord && dfs(word, count + 1, i + 1, new StringBuilder())) {
return true;
}
}
return count > 1 && (wordSet.contains(sb.toString()) || start == word.length());
}
}
相关文章
- MySQL_(Java)【连接池】简单在JDBCUtils.java中创建连接池
- Java实现 LeetCode 819 最常见的单词(暴力)
- Java实现 LeetCode 781 森林中的兔子(分析题)
- Java实现 LeetCode 765 情侣牵手(并查集 || 暴力)
- Java实现 LeetCode 710 黑名单中的随机数(黑白名单)
- Java实现 LeetCode 912 排序数组(用数组去代替排序O(N))
- Java实现 LeetCode 524 通过删除字母匹配到字典里最长单词(又是一道语文题)
- Java实现 LeetCode 523 连续的子数组和(ง •_•)ง
- Java实现 LeetCode 519 随机翻转矩阵
- Java实现 LeetCode 458 可怜的小猪
- Java实现 LeetCode 437 路径总和 III(三)
- Java实现 LeetCode 383 赎金信
- Java实现 LeetCode 374 猜数字大小 II
- Java实现 LeetCode 334 递增的三元子序列
- Java实现 LeetCode 328 奇偶链表
- Java实现 LeetCode 299 猜数字游戏
- Java实现 LeetCode 300 最长上升子序列
- Java实现 LeetCode 97 交错字符串
- Java实现 LeetCode 87 扰乱字符串
- Java实现 LeetCode 78 子集
- Java实现 LeetCode 76 最小覆盖子串
- Java实现 LeetCode 63 不同路径 II(二)
- Java实现 LeetCode 17 电话号码的字母组合
- Java实现 LeetCode 2 两数相加
- Java实现LeetCode_0028_ImplementStrStr
- Java实现LeetCode_0041_FirstMissingPositive
- Java实现 LeetCode 240 搜索二维矩阵 II