[LeetCode] 2452. Words Within Two Edits of Dictionary

You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length.

In one edit you can take a word from queries, and change any letter in it to any other letter. Find all words from queries that, after a maximum of two edits, equal some word from dictionary.

Return a list of all words from queries, that match with some word from dictionary after a maximum of two edits. Return the words in the same order they appear in queries.

Example 1:

Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
Thus, we return ["word","note","wood"].

Example 2:

Input: queries = ["yes"], dictionary = ["not"]
Output: []
Explanation:
Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.

Constraints:

• 1 <= queries.length, dictionary.length <= 100
• n == queries[i].length == dictionary[j].length
• 1 <= n <= 100
• All queries[i] and dictionary[j] are composed of lowercase English letters.

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

给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。

一次 编辑 中，你可以从 queries 中选择一个单词，将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串：不超过 两次编辑内，字符串与 dictionary 中某个字符串相同。

请你返回 queries 中的单词列表，这些单词距离 dictionary 中的单词 编辑次数 不超过 两次 。单词返回的顺序需要与 queries 中原本顺序相同。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/words-within-two-edits-of-dictionary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

读完题感觉这道题跟 word ladder 挺像的，还以为要用 BFS 做，没想到用暴力解就能过。

思路是遍历 queries 中的每个单词，让每个单词都与 dictionary 中的单词一一比较，看看有多少个字母不一样。如果不一样的字母数量 > 2 则说明两次编辑内是没法满足的。

时间O(mn)

空间O(n) - output list

Java实现

 1 class Solution {
 2     public List<String> twoEditWords(String[] queries, String[] dictionary) {
 3         List<String> res = new ArrayList<>();
 4         // corner case
 5         if (queries == null || queries.length == 0) {
 6             return res;
 7         }
 8         
 9         // normal case
10         for (String word : queries) {
11             if (helper(word, dictionary)) {
12                 res.add(word);
13             }
14         }
15         return res;
16     }
17     
18     private boolean helper(String word, String[] dictionary) {
19         int n = word.length();
20         for (String d : dictionary) {
21             int count = 0;
22             for (int i = 0; i < n; i++) {
23                 if (word.charAt(i) != d.charAt(i)) {
24                     count++;
25                     if (count > 2) {
26                         break;
27                     }
28                 }
29             }
30             if (count <= 2) {
31                 return true;
32             }
33         }
34         return false;
35     }
36 }

LeetCode 题目总结