实现一个魔法字典

难度:

标签:

题目描述

代码结果

运行时间: 39 ms, 内存: 16.3 MB

/*
 * 思路：
 * 1. 使用HashSet来存储字典中的单词。
 * 2. 使用流的方式遍历每个字符并替换。
 */
 
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
 
public class MagicDictionary {
    private Set<String> dictionary;
 
    public MagicDictionary() {
        dictionary = new HashSet<>();
    }
 
    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            this.dictionary.add(word);
        }
    }
 
    public boolean search(String searchWord) {
        return IntStream.range(0, searchWord.length())
                .anyMatch(i -> searchWord.chars()
                        .mapToObj(c -> (char) c)
                        .filter(c -> c != searchWord.charAt(i))
                        .anyMatch(c -> {
                            char[] chars = searchWord.toCharArray();
                            chars[i] = c;
                            return dictionary.contains(new String(chars));
                        }));
    }
}

解释

方法:

这个题解首先在构建字典阶段（buildDict），将所有输入的单词按照长度分类存储到一个字典中，其中键是单词的长度，值是具有该长度的单词集合。这样做的目的是为了在搜索阶段能够快速定位到与待搜索单词长度相同的单词集合，从而降低搜索范围。在搜索阶段（search），如果待搜索单词的长度在构建的字典中找不到对应的键，则直接返回False。否则，遍历与搜索词长度相同的单词集合，通过逐字符比对的方式计算两个单词之间的不同字符数。如果恰好有一个字符不同，则返回True，表示可以通过改变一个字符使得单词存在于字典中。如果遍历完都没有找到，返回False。

时间复杂度:

O(N * L)

空间复杂度:

O(N * L)

代码细节讲解

🦆

为什么选择按单词长度来组织字典，而不是其他属性如字母顺序或哈希值？

▷

选择按单词长度来组织字典是基于搜索效率的考虑。由于我们的目标是找到只有一个字符不同的单词，如果单词长度不同，则它们之间的字符数就已经不匹配，从而没有必要进行比较。而按字母顺序或哈希值组织字典可能会导致需要比较长度不同的单词，这不仅增加了比较次数，还可能会导致比较无效。因此，按长度分类可以直接缩小搜寻范围，提高搜索效率。

🦆

在实现search方法时，有没有考虑使用更高效的算法来减少单词间比对的次数？

▷

当前实现中主要使用了逐字符比对的方法，这种方法虽然直接但效率不是最优。可以考虑使用更高效的算法，如构建一个更复杂的数据结构（例如使用字典树Trie结合哈希表），预先计算并存储每个单词去除任一字符后可能的所有字符串形态，然后在搜索时，生成待搜索词的所有可能形态并快速查找这些形态是否存在。这种方法可以大大减少在搜索过程中的比较次数，提高效率。

🦆

buildDict方法中使用set存储同长度的单词有什么特殊考虑？例如考虑到重复单词或者其他因素吗？

▷

使用set来存储同长度的单词主要是为了避免重复。如果字典中多次添加同一个单词，使用set可以自动处理重复的问题，保证每个长度的单词集合中的元素都是唯一的。此外，set的另一个优点是查找效率较高（平均情况下为常数时间复杂度），这对于在搜索阶段快速判断某个单词是否存在很有帮助。

🦆

search方法中，如果遇到多个单词长度相同但每个单词中有多处字符不同，这种情况下如何优化以减少不必要的比对？

▷

在当前实现中，对于每个单词我们都进行了逐字符的比对，这在单词数量多或字符差异多的情况下效率较低。优化方法可以包括使用更高级的字符串比较算法，如位运算或哈希签名方法来快速排除那些差异字符多于一个的单词。另一个方法是，在构建字典时就预计算每个单词去掉每个字符后的模式，并将这些模式存储在一个高效的查找结构中，如哈希表，这样在搜索时可以直接查找模式匹配，从而避免逐个字符的比对。

相关问题

实现 Trie (前缀树)

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数总计不超过 3 * 10⁴ 次

词典中最长的单词

给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。

若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

示例 1：

输入：words = ["w","wo","wor","worl", "world"]
输出："world"
解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。

示例 2：

输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出："apple"
解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 30
所有输入的字符串 words[i] 都只包含小写字母。

为高尔夫比赛砍树键值映射