当前位置： 首页 > news >正文

【华为机试】648. 单词替换

news 2025/8/12 15:57:28

文章目录

  • 648. 单词替换
    • 题目描述
    • 示例 1：
    • 示例 2：
    • 提示：
    • 解题思路
      • 问题分析
      • 核心思想
      • 算法流程图
      • 字典树搜索策略
      • 算法优化策略
      • 复杂度分析对比
    • 算法实现要点
    • 相关题目
    • 完整题解代码

648. 单词替换

题目描述

在英语中，我们有一个叫做 词根(root) 的概念，可以词根 后面 添加其他一些词组成另一个较长的单词——我们称这个词为 衍生词 (derivative)。例如，词根 help，跟随着 继承词 “ful”，可以形成新的单词 “helpful”。

现在，给定一个由许多 词根 组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有 衍生词 用 词根 替换掉。如果 衍生词 有许多可以形成它的 词根，则用 最短 的 词根 替换它。

你需要输出替换之后的句子。

示例 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. 词根替换：用找到的词根替换原单词，如果没找到则保持原样

算法流程图

是
否
是
否
开始
构建字典树
插入所有词根
分割句子为单词
遍历每个单词
在字典树中搜索最短词根
找到词根?
用词根替换单词
保持原单词
添加到结果
还有单词?
拼接结果字符串
结束

字典树搜索策略

搜索原则
是
否
是
否
找到第一个词根就返回
贪心策略
确保是最短的词根
最短优先
字典树搜索
从根节点开始
逐字符匹配
当前节点是词根结尾?
记录当前词根
继续向下搜索
还有字符且有子节点?
返回最短词根

算法优化策略

graph LRA[优化方案] --> B[字典树方法]A --> C[哈希表方法]A --> D[排序+前缀匹配]A --> E[字典排序优化]B --> B1[时间O(N+M)]B --> B2[空间O(词根总长度)]B --> B3[最优解法]C --> C1[时间O(N×M)]C --> C2[空间O(词根总长度)]C --> C3[实现简单]D --> D1[时间O(M×logM+N×M)]D --> D2[空间O(M)]D --> D3[前缀排序]E --> E1[时间O(N+M)]E --> E2[空间O(词根总长度)]E → E3[字典序优化]style B fill:#c8e6c9style C fill:#fff3e0

复杂度分析对比

graph TDA[算法复杂度对比] --> B[字典树方法]A --> C[哈希表暴力]A --> D[排序前缀匹配]A --> E[优化字典树]A --> F[字符串匹配]B --> B1[时间: O(N+M)]B --> B2[空间: O(L)]B --> B3[最优解法]C --> C1[时间: O(N×M×K)]C --> C2[空间: O(M×K)]C --> C3[简单直接]D --> D1[时间: O(M×logM+N×K)]D --> D2[空间: O(M×K)]D --> D3[排序优化]E --> E1[时间: O(N+M)]E --> E2[空间: O(L)]E --> E3[提前终止]F --> F1[时间: O(N×M×K)]F --> F2[空间: O(1)]F --> F3[会超时]style B fill:#4caf50style F fill:#f44336subgraph "说明"G[N: 句子长度]H[M: 词根数量]I[K: 平均词根长度]J[L: 词根总长度]end

算法实现要点

  1. 字典树构建：将词根按字符逐个插入，标记结尾节点
  2. 前缀搜索：对每个单词逐字符搜索，遇到词根结尾立即返回
  3. 贪心策略：找到第一个匹配的词根就停止，保证是最短的
  4. 边界处理：处理空字符串、单字符词根等特殊情况
  5. 性能优化：使用数组代替哈希表提升访问速度

相关题目

  • LeetCode 208. 实现 Trie (前缀树)
  • LeetCode 211. 添加与搜索单词 - 数据结构设计
  • LeetCode 720. 词典中最长的单词
  • LeetCode 820. 单词的压缩编码

完整题解代码

package mainimport ("fmt""sort""strings""time"
)// ========== 方法1: 字典树方法（推荐） ==========// TrieNode 字典树节点
type TrieNode struct {children [26]*TrieNode // 26个小写字母isRoot   bool          // 是否为词根结尾
}// newTrieNode 创建新的字典树节点
func newTrieNode() *TrieNode {return &TrieNode{children: [26]*TrieNode{},isRoot:   false,}
}// Trie 字典树
type Trie struct {root *TrieNode
}// newTrie 创建新的字典树
func newTrie() *Trie {return &Trie{root: newTrieNode()}
}// insert 插入词根到字典树
func (t *Trie) insert(root string) {node := t.rootfor i := 0; i < len(root); i++ {index := root[i] - 'a'if node.children[index] == nil {node.children[index] = newTrieNode()}node = node.children[index]}node.isRoot = true
}// findRoot 查找单词的最短词根
func (t *Trie) findRoot(word string) string {node := t.rootfor i := 0; i < len(word); i++ {index := word[i] - 'a'if node.children[index] == nil {break}node = node.children[index]// 找到词根，立即返回（保证最短）if node.isRoot {return word[:i+1]}}return word // 没找到词根，返回原单词
}func replaceWords1(dictionary []string, sentence string) string {// 构建字典树trie := newTrie()for _, root := range dictionary {trie.insert(root)}// 分割句子并替换words := strings.Split(sentence, " ")for i, word := range words {words[i] = trie.findRoot(word)}return strings.Join(words, " ")
}// ========== 方法2: 哈希表方法 ==========
func replaceWords2(dictionary []string, sentence string) string {// 将词根存储到哈希表rootSet := make(map[string]bool)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] = prefixbreak}}}return strings.Join(words, " ")
}// ========== 方法3: 排序前缀匹配 ==========
func replaceWords3(dictionary []string, sentence string) string {// 按长度排序，确保最短的词根优先匹配sort.Slice(dictionary, func(i, j int) bool {return len(dictionary[i]) < len(dictionary[j])})words := strings.Split(sentence, " ")for i, word := range words {for _, root := range dictionary {if len(root) <= len(word) && strings.HasPrefix(word, root) {words[i] = rootbreak // 找到最短的词根就停止}}}return strings.Join(words, " ")
}// ========== 方法4: 优化字典树（提前终止） ==========// TrieNode2 优化的字典树节点
type TrieNode2 struct {children map[byte]*TrieNode2isRoot   boolrootWord string // 直接存储词根
}// newTrieNode2 创建优化的字典树节点
func newTrieNode2() *TrieNode2 {return &TrieNode2{children: make(map[byte]*TrieNode2),isRoot:   false,rootWord: "",}
}// Trie2 优化的字典树
type Trie2 struct {root *TrieNode2
}// newTrie2 创建优化的字典树
func newTrie2() *Trie2 {return &Trie2{root: newTrieNode2()}
}// insert 插入词根（如果已存在更短的词根，不插入）
func (t *Trie2) insert(root string) {node := t.rootfor i := 0; i < len(root); i++ {char := root[i]// 如果当前路径上已经有词根，且更短，则不需要插入if node.isRoot {return}if node.children[char] == nil {node.children[char] = newTrieNode2()}node = node.children[char]}// 标记为词根，并清空其子节点（因为我们只需要最短的）node.isRoot = truenode.rootWord = rootnode.children = make(map[byte]*TrieNode2)
}// findRoot 查找最短词根
func (t *Trie2) findRoot(word string) string {node := t.rootfor i := 0; i < len(word); i++ {char := word[i]if node.children[char] == nil {break}node = node.children[char]if node.isRoot {return node.rootWord}}return word
}func replaceWords4(dictionary []string, sentence string) string {// 按长度排序，优先插入短的词根sort.Slice(dictionary, func(i, j int) bool {return len(dictionary[i]) < len(dictionary[j])})trie := newTrie2()for _, root := range dictionary {trie.insert(root)}words := strings.Split(sentence, " ")for i, word := range words {words[i] = trie.findRoot(word)}return strings.Join(words, " ")
}// ========== 方法5: 字符串暴力匹配 ==========
func replaceWords5(dictionary []string, sentence string) string {words := strings.Split(sentence, " ")for i, word := range words {minRoot := wordfor _, root := range dictionary {if len(root) < len(minRoot) && strings.HasPrefix(word, root) {minRoot = root}}words[i] = minRoot}return strings.Join(words, " ")
}// ========== 工具函数 ==========// 打印字典树结构
func (t *Trie) printTrie() {fmt.Println("字典树结构:")t.printTrieHelper(t.root, "", "")
}func (t *Trie) printTrieHelper(node *TrieNode, prefix, indent string) {if node.isRoot {fmt.Printf("%s%s [词根]\n", indent, prefix)}for i, child := range node.children {if child != nil {char := byte('a' + i)t.printTrieHelper(child, prefix+string(char), indent+"  ")}}
}// 统计字典树节点数
func (t *Trie) countNodes() int {return t.countNodesHelper(t.root)
}func (t *Trie) countNodesHelper(node *TrieNode) int {count := 1for _, child := range node.children {if child != nil {count += t.countNodesHelper(child)}}return count
}// 获取所有词根
func (t *Trie) getAllRoots() []string {var roots []stringt.getAllRootsHelper(t.root, "", &roots)return roots
}func (t *Trie) getAllRootsHelper(node *TrieNode, prefix string, roots *[]string) {if node.isRoot {*roots = append(*roots, prefix)}for i, child := range node.children {if child != nil {char := byte('a' + i)t.getAllRootsHelper(child, prefix+string(char), roots)}}
}// 生成测试数据
func generateTestCase(rootCount, sentenceLen int) ([]string, string) {// 生成词根roots := make([]string, rootCount)chars := "abcdefghijklmnopqrstuvwxyz"for i := 0; i < rootCount; i++ {length := 2 + i%4 // 长度2-5root := make([]byte, length)for j := 0; j < length; j++ {root[j] = chars[(i*3+j*7)%26]}roots[i] = string(root)}// 生成句子words := make([]string, sentenceLen)for i := 0; i < sentenceLen; i++ {if i%3 == 0 && i/3 < len(roots) {// 部分单词使用词根+后缀root := roots[i/3]suffix := "ing"words[i] = root + suffix} else {// 随机单词length := 3 + i%5word := make([]byte, length)for j := 0; j < length; j++ {word[j] = chars[(i*5+j*11)%26]}words[i] = string(word)}}return roots, strings.Join(words, " ")
}// ========== 测试和性能评估 ==========
func main() {// 测试用例testCases := []struct {name       stringdictionary []stringsentence   stringexpected   string}{{name:       "示例1: 基础替换",dictionary: []string{"cat", "bat", "rat"},sentence:   "the cattle was rattled by the battery",expected:   "the cat was rat by the bat",},{name:       "示例2: 单字符词根",dictionary: []string{"a", "b", "c"},sentence:   "aadsfasf absbs bbab cadsfafs",expected:   "a a b c",},{name:       "测试3: 无匹配",dictionary: []string{"cat", "bat", "rat"},sentence:   "hello world programming",expected:   "hello world programming",},{name:       "测试4: 完全匹配",dictionary: []string{"hello", "world"},sentence:   "hello world",expected:   "hello world",},{name:       "测试5: 多个词根匹配",dictionary: []string{"a", "aa", "aaa"},sentence:   "aaaaaaaaa",expected:   "a",},{name:       "测试6: 长词根",dictionary: []string{"application", "app", "apple"},sentence:   "application development",expected:   "app development",},{name:       "测试7: 空词根",dictionary: []string{},sentence:   "hello world",expected:   "hello world",},{name:       "测试8: 重复词根",dictionary: []string{"cat", "cat", "dog"},sentence:   "the caterpillar and doggy",expected:   "the cat and dog",},{name:       "测试9: 前缀包含",dictionary: []string{"car", "card", "care"},sentence:   "careful careless cards",expected:   "car car car", // car是最短的词根，会被优先匹配},{name:       "测试10: 单词词根",dictionary: []string{"i", "love", "leetcode"},sentence:   "i love solving leetcode problems",expected:   "i love solving leetcode problems",},}// 算法方法methods := []struct {name stringfn   func([]string, string) string}{{"字典树方法", replaceWords1},{"哈希表方法", replaceWords2},{"排序前缀匹配", replaceWords3},{"优化字典树", replaceWords4},{"暴力字符串匹配", replaceWords5},}fmt.Println("=== LeetCode 648. 单词替换 - 测试结果 ===")fmt.Println()// 运行测试for _, tc := range testCases {fmt.Printf("测试用例: %s\n", tc.name)fmt.Printf("词根字典: %v\n", tc.dictionary)fmt.Printf("原句子: %s\n", tc.sentence)allPassed := truevar results []stringvar times []time.Durationfor _, method := range methods {start := time.Now()result := method.fn(tc.dictionary, tc.sentence)elapsed := time.Since(start)results = append(results, result)times = append(times, elapsed)status := "✅"if result != tc.expected {status = "❌"allPassed = false}fmt.Printf("  %s: %s (耗时: %v)\n", method.name, status, elapsed)if result != tc.expected {fmt.Printf("    预期: %s\n", tc.expected)fmt.Printf("    实际: %s\n", result)}}fmt.Printf("期望结果: %s\n", tc.expected)if allPassed {fmt.Println("✅ 所有方法均通过")} else {fmt.Println("❌ 存在失败的方法")}fmt.Println(strings.Repeat("-", 60))}// 字典树演示fmt.Println("\n=== 字典树结构演示 ===")demoTrie()// 性能对比测试fmt.Println("\n=== 性能对比测试 ===")performanceTest()// 算法特性总结fmt.Println("\n=== 算法特性总结 ===")fmt.Println("1. 字典树方法:")fmt.Println("   - 时间复杂度: O(N+M)")fmt.Println("   - 空间复杂度: O(L)")fmt.Println("   - 特点: 最优解法，前缀搜索高效")fmt.Println()fmt.Println("2. 哈希表方法:")fmt.Println("   - 时间复杂度: O(N×K)")fmt.Println("   - 空间复杂度: O(M×K)")fmt.Println("   - 特点: 实现简单，理解容易")fmt.Println()fmt.Println("3. 排序前缀匹配:")fmt.Println("   - 时间复杂度: O(M×logM+N×M×K)")fmt.Println("   - 空间复杂度: O(M×K)")fmt.Println("   - 特点: 排序保证最短优先")fmt.Println()fmt.Println("4. 优化字典树:")fmt.Println("   - 时间复杂度: O(N+M)")fmt.Println("   - 空间复杂度: O(L)")fmt.Println("   - 特点: 提前终止，空间最优")fmt.Println()fmt.Println("5. 暴力字符串匹配:")fmt.Println("   - 时间复杂度: O(N×M×K)")fmt.Println("   - 空间复杂度: O(1)")fmt.Println("   - 特点: 最直接但效率低")// 单词替换演示fmt.Println("\n=== 单词替换演示 ===")demoWordReplacement()
}// 字典树演示
func demoTrie() {fmt.Println("构建词根字典树: [cat, bat, rat]")dictionary := []string{"cat", "bat", "rat"}trie := newTrie()for _, root := range dictionary {trie.insert(root)fmt.Printf("插入词根: %s\n", root)}fmt.Printf("\n字典树节点总数: %d\n", trie.countNodes())fmt.Printf("存储的词根: %v\n", trie.getAllRoots())// 测试单词查找fmt.Println("\n单词查找测试:")testWords := []string{"cattle", "battery", "rattled", "hello"}for _, word := range testWords {root := trie.findRoot(word)if root != word {fmt.Printf("'%s' → '%s' (找到词根)\n", word, root)} else {fmt.Printf("'%s' → '%s' (无词根)\n", word, root)}}
}// 性能测试
func performanceTest() {testSizes := []struct {roots       intsentenceLen int}{{10, 20},{50, 100},{100, 200},{200, 500},}methods := []struct {name stringfn   func([]string, string) string}{{"字典树", replaceWords1},{"哈希表", replaceWords2},{"排序匹配", replaceWords3},{"优化字典树", replaceWords4},}for _, size := range testSizes {fmt.Printf("性能测试 - 词根数: %d, 句子长度: %d\n",size.roots, size.sentenceLen)dictionary, sentence := generateTestCase(size.roots, size.sentenceLen)for _, method := range methods {start := time.Now()result := method.fn(dictionary, sentence)elapsed := time.Since(start)wordCount := len(strings.Split(result, " "))fmt.Printf("  %s: 耗时=%v, 处理单词=%d\n",method.name, elapsed, wordCount)}fmt.Println()}
}// 单词替换演示
func demoWordReplacement() {fmt.Println("单词替换场景演示:")// 场景1: 动物相关fmt.Println("\n场景1: 动物词汇替换")dictionary1 := []string{"cat", "dog", "bird"}sentence1 := "the cats and dogs are flying like birds"result1 := replaceWords1(dictionary1, sentence1)fmt.Printf("词根: %v\n", dictionary1)fmt.Printf("原句: %s\n", sentence1)fmt.Printf("替换: %s\n", result1)// 场景2: 技术词汇fmt.Println("\n场景2: 技术词汇替换")dictionary2 := []string{"program", "develop", "test", "debug"}sentence2 := "programming development testing debugging"result2 := replaceWords1(dictionary2, sentence2)fmt.Printf("词根: %v\n", dictionary2)fmt.Printf("原句: %s\n", sentence2)fmt.Printf("替换: %s\n", result2)// 场景3: 多层次词根fmt.Println("\n场景3: 多层次词根替换")dictionary3 := []string{"a", "ap", "app", "appl", "apple"}sentence3 := "application appreciate apple"result3 := replaceWords1(dictionary3, sentence3)fmt.Printf("词根: %v\n", dictionary3)fmt.Printf("原句: %s\n", sentence3)fmt.Printf("替换: %s\n", result3)fmt.Println("\n单词替换演示完成!")
}
http://www.xdnf.cn/news/1282681.html

相关文章：

  • Jmeter使用第二节-接口测试（Mac版）
  • Nestjs框架: RBAC基于角色的权限控制模型初探
  • Flutter - 应用启动/路由管理
  • buildroot编译qt 5.9.8 arm64版本踩坑
  • 个人效能是一个系统
  • MaixPy简介
  • MySQL 函数
  • 达梦数据库慢SQL日志收集和分析
  • 【排序算法】⑥快速排序：Hoare、挖坑法、前后指针法
  • 算法训练营DAY57 第十一章：图论part07
  • 数集相等定义凸显解析几何几百年重大错误：将无穷多各异点集误为同一集
  • 深度学习和神经网络最基础的mlp，从最基础的开始讲
  • 数据大集网：精准获客新引擎，助力中小企业突破推广困局
  • MATLAB实现遗传算法求解路网路由问题
  • R语言机器学习算法实战系列（二十七）LASSO 与 Adaptive LASSO 在特征选择中的比较与应用
  • 【Leetcode】随笔
  • 深入浅出设计模式——行为型模式之观察者模式 Observer
  • Note4：Self-Attention
  • 能力评估：如何系统评估你的技能和经验
  • @ContextConfiguration
  • 嵌入式学习的第四十八天-中断+OCP原则
  • 矩阵游戏（二分图最大匹配）
  • 新人该如何将不同的HTML、CSS、Javascript等文件转化为Vue3文件架构
  • 大数据量下分页查询性能优化实践（SpringBoot+MyBatis-Plus）
  • Linux操作系统从入门到实战（十九）进程状态
  • HyperMesh许可使用监控
  • 从“目标烂尾”到“100%交付”：谷歌OKR追踪系统如何用“透明化+强问责”打造职场责任闭环
  • MD5：理解MD5 / MD5核心特性 / MD5 在前端开发中的常见用途 / 在线生成MD5 / js-md5
  • Spring Boot 2.6.0+ 循环依赖问题及解决方案
  • Android 16 的用户和用户组定义