猜字谜
难度:
标签:
题目描述
代码结果
运行时间: 455 ms, 内存: 38.0 MB
/*
* 思路:
* 1. 对于每一个谜面puzzle,首先找到其第一个字母。
* 2. 使用Java Stream对单词列表进行过滤,检查每一个单词是否包含谜面的第一个字母,并且单词的所有字母都在谜面中。
* 3. 计数符合条件的单词。
* 4. 对每个谜面重复上述步骤,并将结果存入答案数组。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
return Arrays.stream(puzzles).map(puzzle -> {
char firstChar = puzzle.charAt(0);
Set<Character> puzzleSet = puzzle.chars().mapToObj(c -> (char) c).collect(Collectors.toSet());
return (int) Arrays.stream(words).filter(word -> word.indexOf(firstChar) != -1)
.filter(word -> word.chars().allMatch(c -> puzzleSet.contains((char) c)))
.count();
}).collect(Collectors.toList());
}
}
解释
方法:
本题解采用位运算和哈希表的方法来减少搜索空间和提高效率。首先,将每个单词转换成一个整数表示,这个整数的二进制形式中,每一位代表一个字母是否出现在单词中。然后,使用哈希表统计每个整数表示出现的次数。对于每个谜题,首先保证谜题的第一个字母在单词中出现,然后生成谜题可能的所有子集表示,并查询这些子集在之前统计的哈希表中的出现次数,将它们累加得到结果。
时间复杂度:
O(W * L + P * 64)
空间复杂度:
O(W + P)
代码细节讲解
🦆
在算法中,为什么选择使用位运算来表示每个单词和谜题中的字母?
▷🦆
如何确保在进行位运算时不会出现整数溢出,尤其是当字母种类多时(例如不止26个英文字母)?
▷🦆
在生成谜题的所有有效子集表示时,为什么选择从1开始而不是0?这样做有什么特别的优势吗?
▷🦆
算法中提到的哈希表统计每个整数表示出现的次数,这种方法在哪些情况下可能导致效率低下?
▷