Very simple Java


  • 0
    A
    public class WordDictionary {
    
    // '{' is the next char after 'z' in ASCII
    private static final char END = '{';
    
    private class Node {
        char val;
        Node[] children = new Node[27];
        
        public Node(char val) { this.val = val; }
        
        public Node add(char c) {
            int i = c - 'a';
            if (children[i] == null) 
                children[i] = new Node(c);
            return children[i];
        }
        
        public boolean isEnd() {
            return children[26] != null;
        }
    }
    
    private Node root = new Node(END);
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        insert(root, 0, word);
    }
    
    private void insert(Node root, int i, String word) {
        if (i == word.length())
            root.add(END);
        else {
            Node n = root.add(word.charAt(i));
            insert(n, i+1, word);
        }
    }
    
    // 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(root, 0, word);
    }
    
    private boolean search(Node n, int i, String word) {
        if (i == word.length()) return n.isEnd();
        for (Node c : n.children) {
            if (c == null) continue;
            if (word.charAt(i) == '.' || word.charAt(i) == c.val)
                if (search(c, i+1, word)) return true;
        }
        return false;
    }
    
    }

Log in to reply
 

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