2452.距离字典两次编辑以内的单词：暴力

【LetMeFly】2452.距离字典两次编辑以内的单词：暴力

力扣题目链接：https://leetcode.cn/problems/words-within-two-edits-of-dictionary/

给你两个字符串数组 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 <= 100
• n == queries[i].length == dictionary[j].length
• 1 <= n <= 100
• 所有 queries[i] 和 dictionary[j] 都只包含小写英文字母。

解题方法：暴力匹配

两层遍历遍历两个字符串数组，字符串两两尝试匹配。

对于两个字符串，统计相同位置不同字符的个数，若不超过$2$则合格。

合格后记得break，防止重复加入到答案数组中。

• 时间复杂度$O(n\times len(queries)\times len(dictionary))$
• 空间复杂度$O(1)$，力扣返回值不计入算法空间复杂度

AC代码

C++

/*
 * @LastEditTime: 2026-04-22 23:10:53
 */
class Solution {
inline bool ok(const string& a, const string& b) {
    int diff = 0;
    for (int i = 0; i < a.size(); i++) {
        diff += a[i] != b[i];
    }
    return diff <= 2;
}
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> ans;
        for (string& a : queries) {
            for (string& b : dictionary) {
                if (ok(a, b)) {
                    ans.push_back(a);
                    break;
                }
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源