66ms Prefix Tree (Trie) Java with Explanation
Thought\nWe could build a trie using word in dicts. If two words differ by one character only, they will be within the branches regardless of the mismatched cha
**Thought**\nWe could build a trie using word in dicts. If two words differ by one character only, they will be within the branches regardless of the mismatched character.\n```\nFor example, dict = ["ooo", "ooa"] and search("oxo"), they have one character mismatched, \n\no - o [mismatched here, cntMismatched = 1] - a [mismatched here, cntMismatched = 2, backtrack]\n\t\t\t\t           - o - exhausted [cntMismatched = 1, return true]\n  \n```\n**Code**\n```\n    /** Initialize your data structure here. */\n    \n    private static Node root;\n    public MagicDictionary() {\n        root = new Node();       \n    }\n    \n    /** Build a dictionary through a list of words */\n    public void buildDict(String[] dict) {\n        buildTrie(dict);\n    }\n    \n    private void buildTrie(String[] dict) {\n        Node ptr;\n        for (String word : dict) {\n            ptr = root;\n            for (char ch : word.toCharArray()) {\n                int order = ch - \'a\';\n                if (ptr.children[order] == null)\n                    ptr.children[order] = new Node();\n                ptr = ptr.children[order];\n            }\n            ptr.isWordEnd = true;\n        }\n    }\n    \n    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */\n    public boolean search(String word) {        \n        return dfs(0, word, root, 0);\n    }\n    \n    private boolean dfs(int curId, String word, Node parentPtr, int cntMismatched) {\n        \n        if (cntMismatched > 1) {\n            return false;\n        }\n        \n        if (curId == word.length()) {       \n            return parentPtr.isWordEnd && cntMismatched == 1;\n        }\n\n        \n        for (int i = 0; i < 26; i++) {          \n            int order = word.charAt(curId) - \'a\';\n            if (parentPtr.children[i] == null)\n                continue;       \n            if (order != i) {\n                if (dfs(curId + 1, word, parentPtr.children[i], cntMismatched + 1))\n                    return true;\n            } else {\n                if (dfs(curId + 1, word, parentPtr.children[i], cntMismatched))\n                    return true;\n            }\n        }     \n       \n        return false;\n    }\n    \n    class Node {\n        \n        Node[] children;\n        boolean isWordEnd;\n        \n        public Node() {\n            children = new Node[26];\n            isWordEnd = false;\n        }\n    } \n```\n**I appreciate your VOTE UP (\u25B0\u2579\u25E1\u2579\u25B0)**
[]