Medium

题目描述

在英语中，我们有一个叫做词根的概念，它可以跟随其他一些词来形成另一个更长的词——我们称这个词为衍生词。例如，当词根 “help” 后面跟着词 “ful” 时，我们可以形成衍生词 “helpful”。

给定一个由许多词根组成的词典和一个由空格分隔的单词组成的句子，将句子中的所有衍生词替换为形成它的词根。如果一个衍生词可以被多个词根替换，则用最短长度的词根替换它。

返回替换后的句子。

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

提示：

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写字母组成
  • 1 <= sentence.length <= 10^6
  • sentence 仅由小写字母和空格组成
  • sentence 中单词数在 [1, 1000] 范围内
  • sentence 中每个单词长度在 [1, 1000] 范围内
  • sentence 中每两个连续单词将由恰好一个空格分隔
  • sentence 没有前导或尾随空格

解题思路

这是一个典型的前缀匹配问题，可以用多种方法解决：

方法一：字典树（Trie）

构建字典树存储所有词根，对句子中每个单词从前缀开始匹配，找到最短的匹配词根即可。这是最优解法，特别适合大量查询的场景。

方法二：哈希集合

将所有词根存入哈希集合，对每个单词逐个检查其前缀是否在集合中。由于题目要求最短词根，我们按长度递增检查前缀。

方法三：暴力匹配

对每个单词遍历所有词根，找出能匹配的最短词根。时间复杂度较高，但实现简单。

考虑到词典大小相对固定而查询频繁，推荐使用字典树方法。它能够高效地进行前缀匹配，时间复杂度最优。对于每个单词，我们只需要在字典树中查找一次，就能找到最短的匹配词根。

实现时需要注意：

  1. 构建字典树时标记每个词根的结束位置
  2. 查找时一旦找到词根就立即返回（保证最短）
  3. 如果没有找到匹配的词根，保留原单词

代码实现

class Solution {
public:
    struct TrieNode {
        TrieNode* children[26];
        bool isRoot;
        
        TrieNode() : isRoot(false) {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };
    
    void insert(TrieNode* root, const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isRoot = true;
    }
    
    string findRoot(TrieNode* root, const string& word) {
        TrieNode* node = root;
        string prefix = "";
        
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                break;
            }
            node = node->children[index];
            prefix += c;
            if (node->isRoot) {
                return prefix;
            }
        }
        return word;
    }
    
    string replaceWords(vector<string>& dictionary, string sentence) {
        TrieNode* root = new TrieNode();
        
        for (const string& word : dictionary) {
            insert(root, word);
        }
        
        stringstream ss(sentence);
        string word;
        vector<string> result;
        
        while (ss >> word) {
            result.push_back(findRoot(root, word));
        }
        
        string answer = "";
        for (int i = 0; i < result.size(); i++) {
            if (i > 0) answer += " ";
            answer += result[i];
        }
        
        return answer;
    }
};

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.is_root = False
        
        def insert(root, word):
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.is_root = True
        
        def find_root(root, word):
            node = root
            prefix = ""
            
            for char in word:
                if char not in node.children:
                    break
                node = node.children[char]
                prefix += char
                if node.is_root:
                    return prefix
            return word
        
        root = TrieNode()
        for word in dictionary:
            insert(root, word)
        
        words = sentence.split()
        result = []
        
        for word in words:
            result.append(find_root(root, word))
        
        return " ".join(result)

public class Solution {
    public class TrieNode {
        public TrieNode[] Children = new TrieNode[26];
        public bool IsRoot = false;
    }
    
    private void Insert(TrieNode root, string word) {
        TrieNode node = root;
        foreach (char c in word) {
            int index = c - 'a';
            if (node.Children[index] == null) {
                node.Children[index] = new TrieNode();
            }
            node = node.Children[index];
        }
        node.IsRoot = true;
    }
    
    private string FindRoot(TrieNode root, string word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        
        foreach (char c in word) {
            int index = c - 'a';
            if (node.Children[index] == null) {
                break;
            }
            node = node.Children[index];
            prefix.Append(c);
            if (node.IsRoot) {
                return prefix.ToString();
            }
        }
        return word;
    }
    
    public string ReplaceWords(IList<string> dictionary, string sentence) {
        TrieNode root = new TrieNode();
        
        foreach (string word in dictionary) {
            Insert(root, word);
        }
        
        string[] words = sentence.Split(' ');
        List<string> result = new List<string>();
        
        foreach (string word in words) {
            result.Add(FindRoot(root, word));
        }
        
        return string.Join(" ", result);
    }
}

var replaceWords = function(dictionary, sentence) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.isRoot = false;
        }
    }
    
    function insert(root, word) {
        let node = root;
        for (let char of word) {
            if (!(char in node.children)) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isRoot = true;
    }
    
    function findRoot(root, word) {
        let node = root;
        let prefix = "";
        
        for (let char of word) {
            if (!(char in node.children)) {
                break;
            }
            node = node.children[char];
            prefix += char;
            if (node.isRoot) {
                return prefix;
            }
        }
        return word;
    }
    
    const root = new TrieNode();
    for (let word of dictionary) {
        insert(root, word);
    }
    
    const words = sentence.split(' ');
    const result = [];
    
    for (let word of words) {
        result.push(findRoot(root, word));
    }
    
    return result.join(' ');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
字典树O(D×L + S×W)O(D×L)
哈希集合O(D + S×W×L)O(D×L)

其中：

  • D 为词典中词根的数量
  • L 为词根的平均长度
  • S 为句子中单词的数量
  • W 为句子中单词的平均长度

字典树解法在构建阶段时间复杂度为 O(D×L)，查询阶段为 O(S×W)，总体最优。

相关题目