LeetCode 648. 单词替换

Categories:

题目描述
思路分析
1. 解法一：字典树（Trie）（推荐）
2. 解法二：哈希集合
相似题目

题目描述

✅ 648. 单词替换

思路分析

解法一：字典树（Trie）（推荐）

核心思路：

将所有词根插入字典树

对句子中每个单词，在字典树中查找最短词根前缀

若找到则替换为词根，否则保留原单词

复杂度分析：

时间复杂度：O(d + s)，其中 d 为词根字符总长，s 为句子字符总长

空间复杂度：O(d × 26)，字典树节点数

class Solution {

    // 字典树节点
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        // 构建字典树
        TrieNode root = new TrieNode();
        for (String root1 : dictionary) {
            TrieNode node = root;
            for (char c : root1.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new TrieNode();
                }
                node = node.children[idx];
            }
            // 标记词根结尾
            node.word = root1;
        }

        // 替换句子中每个单词
        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < words.length; i++) {
            if (i > 0) {
                sb.append(' ');
            }
            sb.append(findRoot(root, words[i]));
        }

        return sb.toString();
    }

    // 在字典树中查找单词的最短词根前缀
    private String findRoot(TrieNode root, String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                break;
            }
            node = node.children[idx];
            // 找到词根，直接返回
            if (node.word != null) {
                return node.word;
            }
        }
        return word;
    }
}

// 字典树节点
type TrieNode struct {
    children [26]*TrieNode
    word     string
}

func replaceWords(dictionary []string, sentence string) string {
    // 构建字典树
    root := &TrieNode{}
    for _, root1 := range dictionary {
        node := root
        for _, c := range root1 {
            idx := c - 'a'
            if node.children[idx] == nil {
                node.children[idx] = &TrieNode{}
            }
            node = node.children[idx]
        }
        // 标记词根结尾
        node.word = root1
    }

    // 替换句子中每个单词
    words := strings.Split(sentence, " ")
    for i, word := range words {
        node := root
        for _, c := range word {
            idx := c - 'a'
            if node.children[idx] == nil {
                break
            }
            node = node.children[idx]
            // 找到词根，直接替换
            if node.word != "" {
                words[i] = node.word
                break
            }
        }
    }

    return strings.Join(words, " ")
}

解法二：哈希集合

核心思路：

将所有词根存入哈希集合

对句子每个单词，枚举其所有前缀，取最短匹配词根替换

复杂度分析：

时间复杂度：O(d + s²)，其中 d 为词根字符总长，s 为单词最大长度，枚举前缀时最坏 O(s²)

空间复杂度：O(d)，哈希集合存储所有词根

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        // 将词根存入集合
        Set<String> rootSet = new HashSet<>(dictionary);

        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < words.length; i++) {
            if (i > 0) {
                sb.append(' ');
            }
            String replaced = words[i];
            // 枚举所有前缀，取最短匹配
            for (int j = 1; j <= words[i].length(); j++) {
                String prefix = words[i].substring(0, j);
                if (rootSet.contains(prefix)) {
                    replaced = prefix;
                    break;
                }
            }
            sb.append(replaced);
        }

        return sb.toString();
    }
}

func replaceWords(dictionary []string, sentence string) string {
    // 将词根存入集合
    rootSet := make(map[string]bool, len(dictionary))
    for _, root := range dictionary {
        rootSet[root] = true
    }

    words := strings.Split(sentence, " ")

    for i, word := range words {
        // 枚举所有前缀，取最短匹配
        for j := 1; j <= len(word); j++ {
            prefix := word[:j]
            if rootSet[prefix] {
                words[i] = prefix
                break
            }
        }
    }

    return strings.Join(words, " ")
}

相似题目

题目	难度	考察点
208. 实现 Trie（前缀树）	中等	字典树设计
211. 添加与搜索单词 - 数据结构设计	中等	字典树/DFS
676. 实现一个魔法字典	中等	字典树/哈希
677. 键值映射	中等	字典树
14. 最长公共前缀	简单	字符串前缀
720. 词典中最长的单词	中等	字典树/哈希

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/24608248