跳到主要内容

LeetCode 648. 单词替换

本节目标

把词根存入 Trie，在逐词查询时返回第一个完整前缀。

这道题是字符串综合中的最短前缀查询母题。字典中的词根可以共享前缀，Trie 能在一次逐字符扫描中同时判断路径和完整词根。

查看原题

题意与约束​

给定词根字典和一个由单空格分隔的句子。若单词存在一个或多个词根前缀，就用最短词根替换；若不存在，则保留原单词。

例如字典包含 cat 时，cattle 替换为 cat。若同时包含 a、aa、aaa，所有以 a 开头的单词都应优先使用最短的 a。

为什么第一个结束标记就是答案​

把所有词根插入 Trie 后，从单词首字符开始沿路径查询：

  • 下一条边不存在：没有词根，返回原单词；
  • 到达的节点带有结束标记：当前前缀已经是词根，立即返回；
  • 单词扫描结束仍未见结束标记：返回原单词。

查询从短前缀向长前缀自然推进，因此第一次遇到结束标记时，不需要再比较其他候选。

路径存在不等于词根存在​

Trie 节点存在只说明某个词根经过这里。若没有结束标记，该前缀本身可能并不在字典中。忽略结束标记，会把中间路径错误当成词根。

代码实现​

C++ 用定长子节点下标保存小写字母路径，Python 用嵌套字典保存实际出现的边。两种实现都在第一个结束标记处停止。

C++17
#include <array>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

class Solution {
private:
    struct TrieNode {
        array<int, 26> children;
        bool isEnd;

        TrieNode() : isEnd(false) {
            children.fill(-1);
        }
    };

    vector<TrieNode> trie;

    void insert(const string& root) {
        int node = 0;
        for (char ch : root) {
            int index = ch - 'a';
            if (trie[node].children[index] == -1) {
                trie[node].children[index] = static_cast<int>(trie.size());
                trie.push_back(TrieNode());
            }
            node = trie[node].children[index];
        }
        trie[node].isEnd = true;
    }

    string findRoot(const string& word) const {
        int node = 0;
        for (int index = 0; index < static_cast<int>(word.size()); index++) {
            int child = word[index] - 'a';
            if (trie[node].children[child] == -1) {
                return word;
            }
            node = trie[node].children[child];
            if (trie[node].isEnd) {
                return word.substr(0, index + 1);
            }
        }
        return word;
    }

public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        trie = vector<TrieNode>(1);
        for (const string& root : dictionary) {
            insert(root);
        }

        istringstream sentenceStream(sentence);
        string word;
        string answer;
        while (sentenceStream >> word) {
            if (!answer.empty()) {
                answer += ' ';
            }
            answer += findRoot(word);
        }
        return answer;
    }
};

复杂度分析​

设所有词根总字符数为 D，句子总字符数为 S。建树时间为 O(D)，逐词查询和重组句子为 O(S)，总时间复杂度为 O(D + S)；Trie 空间复杂度为 O(D)。

易错点​

  • 找到词根后继续向下，返回了更长词根。
  • 只检查 Trie 路径，没有检查单词结束标记。
  • 为每个单词遍历整个词根列表，使公共前缀被重复比较。
  • 替换后没有按原顺序用单空格重新连接单词。

模式迁移​

它复用匹配与字典树中的“路径＋结束标记”模型。把“遇到第一个结束标记就返回”改为“尽量走到最深节点”，就能处理最长已有前缀；把返回值改为布尔值，就得到普通前缀查询。