leetcode热题 - 4

距离字典两次编辑以内的单词

问题描述

给你两个字符串数组 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:vector<string>twoEditWords(vector<string>&queries,vector<string>&dictionary){vector<string>ans;for(string query:queries){for(string s:dictionary){intdis=0;for(inti=0;i<query.size();i++){if(query[i]!=s[i]){++dis;}}if(dis<=2){ans.push_back(query);break;}}}returnans;}};

复杂度分析

总结

这道题要求从queries中找出所有与dictionary中任意单词汉明距离不超过 2（即最多修改两个字母就能变成字典中的某个词）的单词，并按原顺序返回。核心解题思路是：因为所有单词等长，所以直接对每个query遍历dictionary中的所有单词，逐位比较计算汉明距离（即对应位置字符不同的个数），一旦找到距离 ≤ 2 的单词，就将该query加入答案并跳过剩余字典（break），最终返回答案列表。该方法本质是三重循环暴力枚举，时间复杂度 O(n × m × L)，但由于单词长度和数组规模通常较小，足以通过题目测试。