距离字典两次编辑以内的单词问题描述给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母且长度都相同。一次 编辑 中你可以从 queries 中选择一个单词将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串不超过 两次编辑内字符串与 dictionary 中某个字符串相同。请你返回 queries 中的单词列表这些单词距离 dictionary 中的单词 编辑次数 不超过 两次 。单词返回的顺序需要与 queries 中原本顺序相同。真题链接距离字典两字编辑以内的单词解题思路这一题的解题思路非常清晰给你两个字符串数组queries和dictionary由于所有字符串的长度都相同因此我们只需要对queries数组中的每一个字符串进行遍历求出其与dictionary字符串数组中每一个单词的汉明距离最后将汉明距离小于2的字符串返回即可得到答案。这里科普一下汉明距离是什么汉明距离表示两个等长字符串之间对应位置的不同字符的个数。它衡量的是两个字符串需要改变多少个位置才能变得完全相同。定义对于两个长度相同的字符串 A 和 B它们的汉明距离就是在相同位置上A 和 B 字符不同的位置的数量。符号通常用 d(A, B) 表示。例子1011101 与 1001001比较每一位第3位(1 vs 0)、第5位(1 vs 0)不同所以汉明距离是 2。karolin 与 kathrin比较每一位第3位(r vs t)、第4位(o vs h)、第5位(l vs r)不同所以汉明距离是 3。12345 与 54321全部5位都不同汉明距离是 5。注意汉明距离要求两个字符串长度必须相等。如果长度不同通常需要先对齐或使用其他距离度量如编辑距离。代码实现classSolution{public:vectorstringtwoEditWords(vectorstringqueries,vectorstringdictionary){vectorstringans;for(string query:queries){for(string s:dictionary){intdis0;for(inti0;iquery.size();i){if(query[i]!s[i]){dis;}}if(dis2){ans.push_back(query);break;}}}returnans;}};复杂度分析复杂度量级时间复杂度O(n × m)空间复杂度O(n)总结这道题要求从queries中找出所有与dictionary中任意单词汉明距离不超过 2即最多修改两个字母就能变成字典中的某个词的单词并按原顺序返回。核心解题思路是因为所有单词等长所以直接对每个query遍历dictionary中的所有单词逐位比较计算汉明距离即对应位置字符不同的个数一旦找到距离 ≤ 2 的单词就将该query加入答案并跳过剩余字典break最终返回答案列表。该方法本质是三重循环暴力枚举时间复杂度 O(n × m × L)但由于单词长度和数组规模通常较小足以通过题目测试。