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

LeetCode 每日一题笔记日期：2026.04.22 题目：2452. 距离字典两次编辑以内的单词

news 2026/4/22 22:48:26

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 时提前终止比较。

算法步骤

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

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)（不包含结果列表的额外空间）
- 仅使用常量级临时变量存储差异计数，无额外数据结构开销。