企业官网建设流程全解析

LeetCode 每日一题笔记

0. 前言

• 日期：2026.04.22
• 题目：2452. 距离字典两次编辑以内的单词
• 难度：中等
• 标签：数组、字符串、字典树

1. 题目理解

问题描述：
给你两个字符串数组queries和dictionary，所有单词均为小写字母且长度相同。一次编辑指将单词中任意一个字母修改为其他字母。返回queries中，与dictionary中任意单词的编辑距离不超过 2 的单词列表，顺序与原queries保持一致。

示例：

输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
输出：["word","note","wood"]
解释：

• “word” 修改 1 次可得到 “wood”；
• “note” 修改 2 次可得到 “joke”；
• “ants” 无法在 2 次编辑内匹配字典中的单词；
• “wood” 无需修改即可匹配字典中的单词。

2. 解题思路

核心观察

• 题目中的“编辑距离”仅包含字符替换，不考虑插入/删除，且所有单词长度相同；
• 对每个query，只需找到字典中任意一个单词，两者的不同字符数 ≤ 2，即可将该query加入结果；
• 可直接暴力比较，对每个query和字典单词逐位统计差异字符数，差异超过 2 时提前终止比较。

算法步骤

1. 初始化结果列表；
2. 遍历queries中的每个单词q；
3. 对每个q，遍历dictionary中的每个单词dic：
   • 逐位比较q和dic，统计差异字符数；
   • 若差异字符数 > 2，提前终止当前dic的比较；
   • 若存在任意dic使差异字符数 ≤ 2，将q加入结果列表并跳出字典循环；
4. 遍历完成后返回结果列表。

3. 代码实现

packagelc2452;importjava.util.ArrayList;importjava.util.List;classSolution{publicList<String>twoEditWords(String[]queries,String[]dictionary){List<String>ans=newArrayList<>();for(inti=0;i<queries.length;i++){for(Stringdic:dictionary){intcount=0;for(intj=0;j<queries[i].length();j++){if(queries[i].charAt(j)!=dic.charAt(j)){count++;}if(count>2){break;}}if(count<=2){ans.add(queries[i]);break;}}}returnans;}}

4. 代码优化说明

优化点1：哈希表预处理（无重复字典词时可选）

将字典单词存入哈希集合，对每个query生成所有 0/1/2 次编辑的变体，检查是否存在于集合中，适用于字典较大的场景（但生成变体的复杂度较高，需权衡）。

优化点2：字典树（Trie）优化

构建字典树存储所有字典单词，对每个query进行深度优先搜索，限制编辑次数 ≤ 2，适用于字典规模较大的场景，可减少重复字符比较。

优化点3：提前终止

原代码已实现差异字符数 > 2 时提前终止当前字典词的比较，避免不必要的遍历，是暴力解法中效率较高的实现。

5. 复杂度分析

• 时间复杂度：O(Q×D×L)O(Q \times D \times L)O(Q×D×L)

  • QQQ：queries的长度；
  • DDD：dictionary的长度；
  • LLL：单词的平均长度；
  • 最坏情况下，每个query需与所有字典词比较，每个比较遍历整个单词长度。

• 空间复杂度：O(1)O(1)O(1)（不包含结果列表的额外空间）

  • 仅使用常量级临时变量存储差异计数，无额外数据结构开销。

6. 总结

• 核心思路是暴力比较 + 提前终止，利用题目限制（仅替换编辑、长度相同）简化问题；
• 关键技巧：差异字符数超过 2 时立即终止当前字典词的比较，避免冗余计算；
• 对于中等规模的输入，暴力解法已足够高效；大规模场景可考虑字典树或哈希变体优化。

关键点回顾

1. 题目中的“编辑距离”仅包含字符替换，无需考虑插入/删除；
2. 差异字符数统计可提前终止，大幅减少比较次数；
3. 结果列表需保持与queries原顺序一致，不可排序后返回。