一、题目描述
给你一个 不含重复 单词的字符串数组 words
,请你找出并返回 words
中的所有 连接词 。
连接词 定义为:一个完全由给定数组中的至少两个较短单词(不一定是不同的两个单词)组成的字符串。
示例 1:
输入:words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] 输出:["catsdogcats","dogcatsdog","ratcatdogcat"] 解释:"catsdogcats" 由 "cats", "dog" 和 "cats" 组成; "dogcatsdog" 由 "dog", "cats" 和 "dog" 组成; "ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。
示例 2:
输入:words = ["cat","dog","catdog"] 输出:["catdog"]
提示:
1 <= words.length <= 10^4
1 <= words[i].length <= 30
words[i]
仅由小写英文字母组成。words
中的所有字符串都是 唯一 的。1 <= sum(words[i].length) <= 10^5
二、解题思路
- 首先,对单词数组按照单词长度进行排序。这样可以确保我们在检查一个单词是否为连接词时,所有可能的组成单词都已经在集合中了。
- 使用一个集合来存储已经遍历过的单词,这样可以在常数时间内检查一个单词是否为连接词。
- 对于每个单词,使用深度优先搜索(DFS)或动态规划(DP)来检查它是否可以由至少两个更短的单词组成。
- 如果一个单词是连接词,则将其添加到结果列表中。
三、具体代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
// 按单词长度排序
Arrays.sort(words, (a, b) -> a.length() - b.length());
Set<String> wordSet = new HashSet<>();
List<String> result = new ArrayList<>();
for (String word : words) {
// 检查当前单词是否为连接词
if (isConcatenatedWord(word, wordSet)) {
result.add(word);
}
// 将当前单词加入集合,供后续单词检查使用
wordSet.add(word);
}
return result;
}
private boolean isConcatenatedWord(String word, Set<String> wordSet) {
if (wordSet.isEmpty()) {
return false;
}
int n = word.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
// 如果当前子串在集合中,并且前面的子串可以由集合中的单词组成
if (dp[j] && wordSet.contains(word.substring(j, i))) {
dp[i] = true;
break;
}
}
}
// 必须由至少两个单词组成
return dp[n] && n != wordSet.stream().filter(w -> w.equals(word)).mapToInt(String::length).findFirst().orElse(0);
}
}
在这个实现中,我们首先按照单词长度对单词数组进行排序,然后使用动态规划来判断每个单词是否是连接词。isConcatenatedWord
方法中,dp[i]
表示字符串 word
的前 i
个字符是否可以由集合 wordSet
中的单词组成。我们检查每个可能的子串,如果它存在于集合中,并且之前的子串可以由集合中的单词组成,那么 dp[i]
被设置为 true
。
此外,为了避免将单个单词错误地标记为连接词,我们确保了连接词至少由两个单词组成,这通过检查 dp[n]
为 true
且单词长度不等于它在集合中的长度来实现。
四、时间复杂度和空间复杂度
1. 时间复杂度
-
排序单词数组:排序的时间复杂度为 O(n log n),其中 n 是单词的数量。
-
遍历单词数组并检查每个单词是否为连接词:对于每个单词,我们需要进行动态规划。动态规划的时间复杂度为 O(m^2),其中 m 是单词的长度。因此,对于所有单词的总时间复杂度为 O(n * m^2)。
-
isConcatenatedWord
方法中的wordSet.contains
操作在哈希集合中平均是 O(1) 的时间复杂度。但是,对于每个单词,我们需要检查所有可能的子串,这会导致 O(m^2) 的操作。
综合以上,总的时间复杂度为 O(n log n + n * m^2),其中 n 是单词的数量,m 是单词的平均长度。
2. 空间复杂度
-
哈希集合
wordSet
用来存储所有单词,其空间复杂度为 O(n * m),其中 n 是单词的数量,m 是单词的平均长度。 -
动态规划数组
dp
的空间复杂度为 O(m),其中 m 是单词的长度。 -
递归调用栈的深度在
isConcatenatedWord
方法中最多为 m,因此递归栈的空间复杂度为 O(m)。
综合以上,总的空间复杂度为 O(n * m + m + m),简化后为 O(n * m),其中 n 是单词的数量,m 是单词的平均长度。
五、总结知识点
-
Java 集合框架:
ArrayList
:用于存储结果列表。HashSet
:用于存储单词集合,以便进行快速的查找操作。List
和Set
接口:分别表示列表和集合的抽象数据类型。
-
Java 数组:
boolean[] dp
:使用布尔数组来实现动态规划,存储子问题的解。
-
Java 8 特性:
Stream API
:在检查连接词时,使用stream().filter().mapToInt().findFirst().orElse()
来找到集合中与当前单词相同长度的单词(这一部分实际上是不必要的,因为dp[n]
已经足够判断单词是否是连接词)。
-
排序:
Arrays.sort
:对字符串数组进行排序,这里使用了 lambda 表达式来定义比较器。
-
字符串操作:
String.substring
:用于获取字符串的子串。
-
动态规划:
- 使用动态规划(DP)来判断一个单词是否可以由集合中的其他单词组成。
dp[i]
表示字符串的前 i 个字符是否可以由集合中的单词组成。
- 使用动态规划(DP)来判断一个单词是否可以由集合中的其他单词组成。
-
递归与迭代:
- 在
isConcatenatedWord
方法中,通过迭代而不是递归来实现动态规划。
- 在
-
逻辑判断:
- 代码中包含了多个 if 语句,用于进行条件判断。
-
面向对象编程:
Solution
类的定义和使用,以及findAllConcatenatedWordsInADict
和isConcatenatedWord
方法的定义,体现了面向对象编程的思想。
-
方法重载与封装:
isConcatenatedWord
方法被封装为私有方法,仅在其所在的类内部使用,这体现了封装的原则。
-
算法设计:
- 整体算法设计包括排序、集合查找、动态规划等,体现了算法设计的基本思路。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
标签:单词,--,复杂度,472,连接词,words,集合,dp From: https://blog.csdn.net/weixin_62860386/article/details/144494897