leetcode
leetcode 1101 ~ 1150
猜字谜

猜字谜

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在算法中,为什么选择使用位运算来表示每个单词和谜题中的字母?
位运算在处理这类问题时具有高效的特点,因为它能够通过整数的位表示来快速地检查字母是否存在,以及进行字母集合的并集和交集操作。每个单词或谜题的字母集合可以被转换成一个整数,其中每个位代表一个字母是否出现(例如,第0位代表'a',第1位代表'b'等)。这种表示方式不仅节省空间,而且利用位运算(如按位与、或和异或)可以高效地实现查询和比对操作,这对于解决涉及大量数据和需要快速响应的算法问题特别有用。
🦆
如何确保在进行位运算时不会出现整数溢出,尤其是当字母种类多时(例如不止26个英文字母)?
确保位运算不会发生整数溢出的一个关键是选择合适的数据类型来存储位表示。在处理只有26个英文字母的情况时,可以使用32位整数(int类型)来存储,因为32位足以表示每个字母是否存在。如果字母种类超过32种,可以选择更大的数据类型,如64位的整数(long类型),甚至可以使用位向量或其他数据结构来管理更多的位。在某些编程语言中,也可以使用库函数来处理大整数或位数组,确保即使在字母种类非常多的情况下也不会溢出。
🦆
在生成谜题的所有有效子集表示时,为什么选择从1开始而不是0?这样做有什么特别的优势吗?
在生成谜题的所有有效子集表示时从1开始,主要是为了确保谜题的第一个字母始终出现在子集中,这是题目的一个要求。从1开始,即设置第一个字母对应的位为1,确保所有生成的子集都至少包含这个字母。这样做的优势在于直接满足了题目对于谜题解答的要求,即每个有效单词必须包含谜题的第一个字母,从而避免了生成无效的子集,提高了算法的效率和准确性。
🦆
算法中提到的哈希表统计每个整数表示出现的次数,这种方法在哪些情况下可能导致效率低下?
哈希表用于统计每个整数表示(即每个字母集合)的出现次数。然而,如果单词数量极大或单词中的字母集合非常分散(即很多单词有独特的字母组合),哈希表中的条目将会非常多,这可能导致内存使用增加。此外,如果哈希函数设计不良,或者遇到大量哈希冲突,也会降低哈希表的查找和插入效率。在极端情况下,这些因素都可能导致算法效率低下。

相关问题