[Java知识库]神奇的字典java实现

class MagicDictionary {
    static class TrieNode{
        TrieNode[] children;
        boolean isWord;
        public TrieNode(){
            children = new TrieNode[26];
        }
    }

    private TrieNode root;
    /** Initialize your data structure here. */
    public MagicDictionary() {
        //创建字典的根节点
        root = new TrieNode();
    }
    //构建字典    
    public void buildDict(String[] dictionary) {
        for(String word : dictionary){
            TrieNode node = root;
            for(char c : word.toCharArray()){
                if(node.children[c - 'a'] == null){
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }
    }
    
    public boolean search(String searchWord) {
        //递归遍历
        return dfs(root,searchWord,0,0);
    }

    public boolean dfs(TrieNode root,String searchWord,int edit,int index){
        if(root == null){
            return false;
        }
        if(root.isWord && index == searchWord.length() && edit == 1){
            return true;
        }
        if(index < searchWord.length() && edit <= 1){
            boolean found = false;
            for(int i = 0;i < 26 && !found;i++){
                int next = i == searchWord.charAt(index) - 'a' ? edit : edit + 1;
                found = dfs(root.children[i],searchWord,next,index + 1);
            }
            return found;
        }
        return false;
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */