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

难度: 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' ，得到 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] 都只包含小写英文字母。

Submission

运行时间: 39 ms

内存: 16.2 MB

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        ans = []
        for _, q in enumerate(queries):
            for _, d in enumerate(dictionary):
                diff = 0
                for i in range(len(q)):
                    if q[i] != d[i]:
                        diff += 1
                    if diff > 2:
                        break
                if diff <= 2:
                    ans.append(q)
                    break
        return ans

Explain

该题解采用了直接的暴力匹配方法来解决问题。对于每个查询词 (queries 中的词)，它会与字典 (dictionary) 中的每个词进行比较。对每一对词，我们逐字符比较两个字符串，计算它们在每个位置上字符不同的数量，这个数量即为编辑距离。如果编辑距离在两次编辑（包括两次）以内，我们就认为这个查询词满足条件，并将其加入结果列表中。一旦一个查询词与字典中的某个词的编辑距离小于等于2，我们就结束对这个查询词的检查，因为我们只需要确定是否存在至少一个这样的字典词即可。

时间复杂度: O(m * k * n)

空间复杂度: O(m)

# 添加了详细注释的题解代码

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        ans = []  # 结果列表
        for _, q in enumerate(queries):  # 遍历每个查询词
            for _, d in enumerate(dictionary):  # 遍历每个字典词
                diff = 0  # 初始化编辑距离计数器
                for i in range(len(q)):  # 比较两个单词的每个字符
                    if q[i] != d[i]:  # 如果字符不同，增加编辑距离
                        diff += 1
                    if diff > 2:  # 如果编辑距离超过2，中断当前比较
                        break
                if diff <= 2:  # 如果编辑距离不超过2
                    ans.append(q)  # 添加到结果列表
                    break  # 中断，不再比较当前查询词与字典中其他词
        return ans  # 返回结果

Explore

在题解的实现中，对于每个查询词（来自queries列表），我们会逐一与字典中的所有单词比较。在比较过程中，我们记录两个单词之间的编辑距离。如果在比较过程中发现某个查询词与字典中某个单词的编辑距离小于或等于2，我们会立即停止对当前查询词的进一步比较。这是因为题目只要求验证是否存在至少一个字典中的单词与查询词的编辑距离在两次以内，一旦找到这样的单词，就无需再继续验证其他字典单词了。

当前的题解代码假设了queries和dictionary中的单词长度相同，因为它使用了固定的索引范围来比较两个字符串的每个字符。如果单词长度不同，这将导致索引错误或不充分的比较。要适应不同长度的单词，应修改代码以首先比较两个单词的长度差，如果长度差大于2，则编辑距离必然超过2；如果长度差在2以内，才进行逐字符比较。此外，逐字符比较时应处理较短单词的末尾，避免越界访问。

在题解中，当比较两个单词的过程中，我们通过逐字符比较来累计不同字符的数量作为编辑距离。一旦这个累计的编辑距离超过2，我们会立刻中断当前的比较。这是通过在循环中使用一个条件判断来实现的：如果`diff > 2`，则使用`break`语句跳出当前的循环。这样做可以避免不必要的比较，提高算法的效率。