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

题目来源：https://leetcode.cn/problems/words-within-two-edits-of-dictionary/

大致题意：
给两个字符串数组：查询数组和字典数组，若查询数组中元素在不超过两次编辑内可以与字典数组中的元素匹配，则表示匹配成功，返回查询数组中所有匹配成功的元素

字符串的一次编辑即为将某个字符换成任意其他字符，在本题中限定字符为小写字母

思路

因为本题的数据范围较小，直接使用哈希表存下字典数组，然后枚举查询数组元素的所有可能的编辑结果也是可以的。设查询数组长度为 n，字符串平均长度为 k，那么时间复杂度为 O(26²nk²)

但是这类给定字典查询字符串的题目，更为简洁方便的实现方案应该是使用前缀树。

对于该题，首先根据字典数组生成前缀树，然后在前缀中匹配查询数组中的元素

因为该题允许两次编辑，所以前缀树的搜索方法需要做出改变，即在前缀树的搜索方法中加上当前可用的编辑次数，若在匹配字符串过程可以根据当前剩余编辑次数决定下一步操作：

1. 若编辑次数大于 0，则当前字符串的匹配结果可以为在当前树节点的所有子节点中匹配剩余子串的结果进行或运算得到的，即只要有一个子节点匹配成功即可。若所有子节点都未匹配成功，则进入下一步
2. 若当前字符对应的子节点为空，则表示匹配失败，返回结果；否则进入下一步
3. 将当前节点更新为字符对应的子节点

那么解题思路可以概括为

1. 初始化前缀树
2. 将字典数组元素插入前缀树
3. 在前缀树中匹配查询数组中的元素，若匹配成功则放入答案数组

代码：

public class TwoEditWords {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        List<String> ans = new ArrayList<>();
        // 初始化前缀树
        Trie trie = new Trie();
        // 将字典数组元素插入前缀树
        for (String str : dictionary) {
            trie.insert(str);
        }
        // 在前缀树中匹配查询数组中的元素
        for (String query : queries) {
            // 若匹配成功则放入答案数组
            if (trie.search(query, 2)) {
                ans.add(query);
            }
        }

        return ans;
    }

    // 前缀树节点类
    class Trie {
        Trie[] children;
        boolean isEnd;  // 表示当前节点是否是某个单词的结尾

        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        // 将 word 插入当前节点
        public void insert(String word) {
            Trie trie = this;
            for (int i = 0; i < word.length(); i++) {
                int idx = word.charAt(i) - 'a';
                if (trie.children[idx] == null) {
                    trie.children[idx] = new Trie();
                }
                trie = trie.children[idx];
            }
            trie.isEnd = true;
        }

        /**
         * 在当前节点中匹配 word
         *
         * @param word  待匹配字符串
         * @param count 剩余编辑次数
         * @return
         */
        public boolean search(String word, int count) {
            Trie trie = this;
            for (int i = 0; i < word.length(); i++) {
                // 如果剩余编辑次数大于 0，尝试在所有子结点中匹配剩余字符
                if (count > 0) {
                    for (int j = 0; j < 26; j++) {
                        // 如果有一个子节点匹配成功，表示该字符串可以匹配，直接返回结果
                        if (trie.children[j] != null && trie.children[j].search(word.substring(i + 1), count - 1)) {
                            return true;
                        }
                    }
                }
                int idx = word.charAt(i) - 'a';
                if (trie.children[idx] == null) {
                    return false;
                }
                trie = trie.children[idx];
            }
            return trie.isEnd;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72