leetcode
leetcode 1851 ~ 1900
统计追加字母可以获得的单词数

统计追加字母可以获得的单词数

难度:

标签:

题目描述

代码结果

运行时间: 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的单词移除一个字母并重新排列得到startWords中的某个单词。通过检查移除每个字母后的单词是否存在于startWords的转换集合中,可以有效地确定是否有对应的匹配单词。尽管这种方法涉及多次操作,但由于使用位运算和集合操作,它仍然是效率较高的。考虑到每个单词的长度通常很短,这种方法的时间复杂度是可接受的。
🦆
如果targetWords中的单词包含重复字母,如何处理?例如,单词'hello'移除一个'l'后,如何确保正确地表示剩余的单词?
位运算的表示方法只关心字母是否出现,而不关心字母出现的次数。当从含有重复字母的单词中移除一个字母时,位运算表示的整数中相应的位只会从1变为0,如果原单词中该字母出现多次,那么在移除一个后,位表示不会变化。因此,这种情况下的处理仍然是有效的,因为我们关心的是能否通过重新排列和添加一个字母来匹配,而不是字母的具体数量。

相关问题