LeetCode 题解工作台
距离字典两次编辑以内的单词
给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。 一次 编辑 中，你可以从 queries 中选择一个单词，将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串： 不超过 两次编辑内，字符串与 dict…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·string
答案摘要
我们直接遍历数组 中的每个单词 ，再遍历数组 中的每个单词 ，如果存在一个单词 与 的编辑距离小于 ，则将 加入答案数组中，然后退出内层循环的遍历。如果不存在这样的单词 ，则继续遍历下一个单词 。 时间复杂度 $O(m \times n \times l)$，其中 和 分别是数组 和 的长度，而 是单词的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·string 题型思路
题目描述
给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。
一次 编辑 中，你可以从 queries 中选择一个单词，将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串：不超过 两次编辑内，字符串与 dictionary 中某个字符串相同。
请你返回 queries 中的单词列表，这些单词距离 dictionary 中的单词 编辑次数 不超过 两次 。单词返回的顺序需要与 queries 中原本顺序相同。
示例 1：
输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"] 输出：["word","note","wood"] 解释： - 将 "word" 中的 'r' 换成 'o' ，得到 dictionary 中的单词 "wood" 。 - 将 "note" 中的 'n' 换成 'j' 且将 't' 换成 'k' ，得到 "joke" 。 - "ants" 需要超过 2 次编辑才能得到 dictionary 中的单词。 - "wood" 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。 所以我们返回 ["word","note","wood"] 。
示例 2：
输入：queries = ["yes"], dictionary = ["not"] 输出：[] 解释： "yes" 需要超过 2 次编辑才能得到 "not" 。 所以我们返回空数组。
提示：
1 <= queries.length, dictionary.length <= 100n == queries[i].length == dictionary[j].length1 <= n <= 100- 所有
queries[i]和dictionary[j]都只包含小写英文字母。
解题思路
方法一：暴力枚举
我们直接遍历数组 中的每个单词 ，再遍历数组 中的每个单词 ，如果存在一个单词 与 的编辑距离小于 ，则将 加入答案数组中，然后退出内层循环的遍历。如果不存在这样的单词 ，则继续遍历下一个单词 。
时间复杂度 ，其中 和 分别是数组 和 的长度，而 是单词的长度。
class Solution:
def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
ans = []
for s in queries:
for t in dictionary:
if sum(a != b for a, b in zip(s, t)) < 3:
ans.append(s)
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on whether brute-force or Trie is used: brute-force is O(Q _D_ N) for Q queries, D dictionary words, and word length N. Trie approach reduces redundant comparisons but may require extra space for the Trie nodes, giving space complexity proportional to total characters in the dictionary. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Watch for queries that are already in the dictionary to avoid unnecessary edits.
- question_mark
Check that edits do not exceed two; counting differences incorrectly can fail test cases.
- question_mark
Consider word length constraints to avoid index errors when comparing characters.
常见陷阱
外企场景- error
Failing to count zero-edit matches when a query word exactly matches a dictionary word.
- error
Stopping comparisons too early or too late, leading to incorrect inclusion or exclusion.
- error
Assuming all words have unique lengths; ensure all queries and dictionary words have the same length.
进阶变体
外企场景- arrow_right_alt
Allowing up to k edits instead of exactly two edits for a more general version.
- arrow_right_alt
Returning the number of edits needed for each matching query instead of just the words.
- arrow_right_alt
Checking for subsequence edits instead of single-character replacements.