# 2452. Words Within Two Edits of Dictionary
###### tags: `Leetcode` `Medium` `Trie` `DFS`
Link: https://leetcode.com/problems/words-within-two-edits-of-dictionary/description/
## 思路
把所有dictionary里面的word都存进trie里
然后dfs搜queries里面的每个单词看trie里有没有和它只差两个字母的单词
## Code

class Solution {
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
    }
    TrieNode root;
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        root = new TrieNode();
        for(String word:dictionary) addWord(word, root);
        List<String> ans = new ArrayList<>();
        for(String q:queries){
            if(find(q, root, 2, 0)) ans.add(q);
        }
        return ans;
    }

    public void addWord(String word, TrieNode root){
        TrieNode curr = root;
        for(int i=0; i<word.length(); i++){
            if(curr.children[word.charAt(i)-'a']==null) curr.children[word.charAt(i)-'a'] = new TrieNode();
            curr = curr.children[word.charAt(i)-'a'];
        }
    }
    
    public boolean find(String word, TrieNode root, int edits, int idx){
        if(edits<0) return false;
        if(idx==word.length()) return true;
        for(int i=0; i<26; i++){
            if(root.children[i]==null) continue;
            if(i==word.charAt(idx)-'a' && find(word, root.children[i], edits, idx+1)) return true;
            else if(find(word, root.children[i], edits-1, idx+1)) return true;
        }
        return false;
    }
}