单词替换

难度:

标签:

题目描述

代码结果

运行时间: 86 ms, 内存: 31.7 MB

/* 
 * 思路： 
 * 1. 使用HashSet存储词根以便快速查找。 
 * 2. 使用Java Stream对句子中的每个单词进行处理，查找其最短词根进行替换。 
 * 3. 拼接所有替换后的单词形成最终句子。 
 */ 
import java.util.*; 
import java.util.stream.*; 
 
class Solution { 
    public String replaceWords(List<String> dictionary, String sentence) { 
        Set<String> dictSet = new HashSet<>(dictionary); 
        return Arrays.stream(sentence.split(" ")) 
                .map(word -> { 
                    for (int i = 1; i <= word.length(); i++) { 
                        if (dictSet.contains(word.substring(0, i))) { 
                            return word.substring(0, i); 
                        } 
                    } 
                    return word; 
                }) 
                .collect(Collectors.joining(" ")); 
    } 
}

解释

方法:

该题解使用了字典树（Trie）来存储词根，并通过在字典树中查找单词的前缀来实现单词替换。具体思路如下： 1. 将词典中的所有词根插入到字典树中 2. 将句子按空格分割成单词列表 3. 对于每个单词，在字典树中查找其最短的词根前缀，并用该前缀替换原单词 4. 将替换后的单词列表拼接成最终的句子

时间复杂度:

O((m+n)*w)，其中 m 为词根数量，n 为句子中的单词数量，w 为单词的平均长度

空间复杂度:

O(m*w + n)，其中 m 为词根数量，w 为词根的平均长度，n 为句子中的单词数量

代码细节讲解

🦆

在构建字典树时，你如何处理相同的词根重复插入的情况？是否有机制避免重复节点的创建？

▷

在构建字典树时，如果词根重复插入，字典树的设计确保不会创建重复的节点。具体来说，当插入一个词根时，从字典树的根节点开始，对词根中的每一个字符进行遍历。如果该字符已经存在于当前节点的子节点中，则直接沿着该子节点继续遍历下一个字符；如果不存在，则创建一个新的子节点，并继续遍历。这样的设计确保了即使同一个词根被多次插入，也只会在第一次插入时创建必要的节点，后续的插入只会重复遍历这些节点，而不会创建新节点。

🦆

在查找单词最短词根前缀时，如果单词完全匹配多个词根长度，比如'cattle'既匹配'cat'又匹配'cattle'，该如何选择用哪个词根进行替换？

▷

在查找单词的最短词根前缀时，根据题解的逻辑，优先选择最短的词根进行替换。这意味着，如果单词'cattle'既匹配'cat'又匹配'cattle'，则会选择'cat'作为替换词根。这是因为一旦在字典树中遍历到一个标记为词根结尾的节点（即节点的`count`属性大于0），就会停止遍历并使用当前的词根前缀替换原单词。这种策略旨在使用尽可能短的词根来实现替换，以减少单词的长度，提高语句的简洁性。

🦆

为什么在字典树的节点中使用`count`属性来标记是否为词根结尾，而不是使用更直观的布尔类型？

▷

在字典树的节点中使用`count`属性而非布尔类型来标记是否为词根结尾，可能是为了提供更多的灵活性和信息。虽然在当前的题解中，`count`属性似乎只用于区分是（1）或否（0）是一个词根的结尾，但使用整数类型的`count`可以允许未来的扩展，例如记录某个词根在词典中出现的次数或其他相关的统计信息。此外，这种方式也可以方便地进行修改以应对不同的需求，而不仅仅是标记存在与否。

🦆

在实际应用中，替换后的单词列表拼接成句子的过程中，如何处理原句子中的标点符号和特殊字符？

▷

在处理替换后的单词列表拼接成句子时，原题解中没有特别说明如何处理标点符号和特殊字符。理想的处理方式应该是在分割句子为单词列表之前，先识别并保留这些标点和特殊字符的位置信息。在进行单词替换后，再根据这些保留的位置信息将单词和标点符号按原来的顺序重新组合。这样可以确保句子的原始结构在替换过程中不受影响，保持语义和语法的正确性。如果题解中没有处理这一点，那么在实际应用中可能需要对该算法进行扩展，以支持对非字母字符的正确处理。

相关问题

实现 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⁴ 次

回文子串 Dota2 参议院