My simple JAVA trie solution


  • 0
    C
    public class WordDictionary {
    public static void main(String[] args) {
        WordDictionary dictionary = new WordDictionary();
        dictionary.addWord("dada");
        System.out.println(dictionary.search("...d"));
    }
    
    Node root = new Node(' ');
    
    public void addWord(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            Node child = node.children.get(c);
            if (child == null) {
                child = new Node(c);
                node.children.put(c, child);
            }
            if (i == word.length() - 1) child.isLeaf = true;
            node = child;
        }
    }
    
    
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        return search(word, 0, root);
    }
    
    private boolean search(String word, int index, Node node) {
        if (node == null) return false;
        if (index == word.length()) return node.isLeaf;
    
        char c = word.charAt(index);
        if (c == '.') {
            for (char j = 'a'; j <= 'z'; j++) {
                boolean res = search(word, index + 1, node.children.get(j));
                if (res) return true;
            }
            return false;
        } else {
            return search(word, index + 1, node.children.get(c));
        }
    
    }
    
    
    static class Node {
        boolean isLeaf = false;
        char c;
        Map<Character, Node> children = new HashMap<>();
    
        Node(char c) {
            this.c = c;
        }
    
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.