统计追加字母可以获得的单词数
难度:
标签:
题目描述
代码结果
运行时间: 375 ms, 内存: 33.1 MB
// Java Stream Solution
// 思路:
// 1. 将 startWords 转化为字符集合,使用流操作来简化代码。
// 2. 对于 targetWords 中的每个单词,移除一个字符后检查是否在 startWords 的集合中。
// 3. 使用流的映射和过滤操作来计算符合条件的 targetWords 数量。
import java.util.*;
import java.util.stream.*;
public class StreamSolution {
public int wordCount(String[] startWords, String[] targetWords) {
Set<String> startSet = Arrays.stream(startWords)
.map(word -> word.chars().sorted().mapToObj(c -> (char) c).collect(StringBuilder::new, StringBuilder::append, StringBuilder::append).toString())
.collect(Collectors.toSet());
return (int) Arrays.stream(targetWords)
.filter(target -> IntStream.range(0, target.length())
.mapToObj(i -> new StringBuilder(target).deleteCharAt(i).toString())
.anyMatch(modified -> startSet.contains(modified.chars().sorted().mapToObj(c -> (char) c).collect(StringBuilder::new, StringBuilder::append, StringBuilder::append).toString()))
.count();
}
}
解释
方法:
题解采用位运算来优化字符串比较的速度。首先,将 startWords 中的每个单词转换为一个整数,该整数的每个位表示一个字母是否存在于单词中。例如,若单词中含有字母 'a',则整数的第0位为1;若含有 'b',则第1位为1,依此类推。这样,每个单词可以表示为一个长度为26的位向量。同样的转换也应用于 targetWords。对于 targetWords 中的每个单词,检查通过移除任意一个字母后是否能在之前生成的 startWords 的整数集合中找到对应的整数。如果可以找到,说明该 targetWord 可以由 startWord 通过添加一个字母并重新排列得到。
时间复杂度:
O((N + M) * L)
空间复杂度:
O(N)
代码细节讲解
🦆
为什么在处理startWords时,选择使用位运算来表示每个单词,而不是使用其他数据结构如哈希表或数组?
▷🦆
在题解中,对于targetWords的每个单词,为什么需要尝试移除每个字母并检查结果,这种方法是否最优?
▷🦆
如果targetWords中的单词包含重复字母,如何处理?例如,单词'hello'移除一个'l'后,如何确保正确地表示剩余的单词?
▷