Medium

题目描述

给你两个字符串数组 queries 和 dictionary。数组中所有字符串都由小写英文字母组成且长度相同。

一次编辑中，你可以从 queries 中取出一个单词，将其中任何一个字母改成任何其他字母。找出 queries 中所有可以经过最多两次编辑后与 dictionary 中某个单词相等的单词。

返回 queries 中经过最多两次编辑后可以与 dictionary 中某个单词匹配的所有单词列表。返回的单词应当按照在 queries 中出现的顺序排列。

示例 1：

输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
输出：["word","note","wood"]
解释：
- 将 "word" 中的 'r' 改为 'o' 可以得到字典单词 "wood"。
- 将 "note" 中的 'n' 改为 'j'，'t' 改为 'k' 可以得到 "joke"。
- "ants" 需要超过 2 次编辑才能匹配字典中的单词。
- "wood" 可以保持不变（0 次编辑）匹配字典中对应的单词。
因此，返回 ["word","note","wood"]。

示例 2：

输入：queries = ["yes"], dictionary = ["not"]
输出：[]
解释：对 "yes" 应用任何两次编辑都无法使其等于 "not"。因此，返回空数组。

提示：

  • 1 <= queries.length, dictionary.length <= 100
  • n == queries[i].length == dictionary[j].length
  • 1 <= n <= 100
  • 所有 queries[i] 和 dictionary[j] 都由小写英文字母组成。

解题思路

这道题要求找出 queries 中能够通过最多两次字符编辑操作与 dictionary 中某个单词匹配的所有单词。

思路分析

由于题目给出的约束条件较小（数组长度最多 100，字符串长度最多 100），我们可以采用暴力枚举的方法：

  1. 核心思想：对于 queries 中的每个单词，检查它与 dictionary 中每个单词的字符差异数量
  2. 字符差异计算：由于所有字符串长度相同，我们只需要逐位比较字符，统计不同字符的个数
  3. 判断条件：如果某个 query 单词与 dictionary 中任意一个单词的字符差异数 ≤ 2，则该 query 单词满足条件

算法步骤

  1. 遍历 queries 中的每个单词 query
  2. 对于每个 query，遍历 dictionary 中的所有单词 word
  3. 计算 query 和 word 之间的字符差异数（即需要编辑的字符个数）
  4. 如果差异数 ≤ 2，则将 query 加入结果列表，并跳出内层循环
  5. 继续处理下一个 query

这种方法时间复杂度为 O(Q × D × N)，其中 Q 是 queries 长度，D 是 dictionary 长度，N 是字符串长度。在给定约束下完全可行。

代码实现

class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> result;
        
        for (const string& query : queries) {
            bool found = false;
            for (const string& word : dictionary) {
                int diff = 0;
                for (int i = 0; i < query.length(); i++) {
                    if (query[i] != word[i]) {
                        diff++;
                    }
                }
                if (diff <= 2) {
                    found = true;
                    break;
                }
            }
            if (found) {
                result.push_back(query);
            }
        }
        
        return result;
    }
};

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        result = []
        
        for query in queries:
            for word in dictionary:
                diff = sum(1 for i in range(len(query)) if query[i] != word[i])
                if diff <= 2:
                    result.append(query)
                    break
        
        return result

public class Solution {
    public IList<string> TwoEditWords(string[] queries, string[] dictionary) {
        var result = new List<string>();
        
        foreach (string query in queries) {
            bool found = false;
            foreach (string word in dictionary) {
                int diff = 0;
                for (int i = 0; i < query.Length; i++) {
                    if (query[i] != word[i]) {
                        diff++;
                    }
                }
                if (diff <= 2) {
                    found = true;
                    break;
                }
            }
            if (found) {
                result.Add(query);
            }
        }
        
        return result;
    }
}

var twoEditWords = function(queries, dictionary) {
    const result = [];
    
    for (const query of queries) {
        let found = false;
        for (const word of dictionary) {
            let diff = 0;
            for (let i = 0; i < query.length; i++) {
                if (query[i] !== word[i]) {
                    diff++;
                }
            }
            if (diff <= 2) {
                found = true;
                break;
            }
        }
        if (found) {
            result.push(query);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(Q × D × N)，其中 Q 是 queries 的长度，D 是 dictionary 的长度，N 是字符串的长度
空间复杂度O(1)，除了存储结果外，只使用了常数额外空间

相关题目