My simple and clean Java code


  • 57
    L

    Using backtrack to check each character of word to search.

    public class WordDictionary {
        public class TrieNode {
            public TrieNode[] children = new TrieNode[26];
            public String item = "";
        }
        
        private TrieNode root = new TrieNode();
    
        public void addWord(String word) {
            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.item = word;
        }
    
        public boolean search(String word) {
            return match(word.toCharArray(), 0, root);
        }
        
        private boolean match(char[] chs, int k, TrieNode node) {
            if (k == chs.length) return !node.item.equals("");   
            if (chs[k] != '.') {
                return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
            } else {
                for (int i = 0; i < node.children.length; i++) {
                    if (node.children[i] != null) {
                        if (match(chs, k + 1, node.children[i])) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }

  • -2
    H

    Very similar solution as yours. But in this case, I think char array is better than substring. Thanks for sharing!

    Cheers!

    public class WordDictionary {
    public class TrieNode{
    String item;
    TrieNode[] children;
    public TrieNode(){
    item = "";
    children = new TrieNode[26];
    }
    public TrieNode getChild(char c){
    return children[c-'a'];
    }
    public void setChild(char c, TrieNode node){
    children[c-'a'] = node;
    }
    }
    TrieNode root = new TrieNode();

    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            if(curr.getChild(c) == null)
                curr.setChild(c, new TrieNode());
            curr = curr.getChild(c);
        }
        curr.item = 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(word, root);
    }
    
    public boolean search(String word, TrieNode node){
        if(word.length() <1)
            return node!=null && !node.item.equals("");
        TrieNode curr = node;
        char c = word.charAt(0);
        if(c != '.' && node.getChild(c)!=null){
            return search(word.substring(1), node.getChild(c));
        }else if(c == '.'){
            for(char i= 'a'; i <= 'z'; i++){
                if(node.getChild(i) != null && search(word.substring(1), node.getChild(i)))
                    return true;
            }
            return false;
        }else
            return false;
    }
    

    }


  • 0
    E

    No, I don't think yours is supposed to be faster than the original one. When substring is used, a new object is created every time, which is time consuming. You should instead use start index so that you can always keep the original string as is and moving index only.


  • 29
    W

    I think we can use boolean variable isWord, it is easier to understand.

    public class WordDictionary {
    
        public class TrieNode {
            public TrieNode[] children = new TrieNode[26];
            public boolean isWord;
        }
        
        private TrieNode root = new TrieNode();
    
        // Adds a word into the data structure.
        public void addWord(String word) {
            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;
        }
    
        // 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 match(word.toCharArray(), 0, root);
        }
        
        private boolean match(char[] chs, int k, TrieNode node) {
            if (k == chs.length) {
                return node.isWord;
            }
            if (chs[k] == '.') {
                for (int i = 0; i < node.children.length; i++) {
                    if (node.children[i] != null && match(chs, k + 1, node.children[i])) {
                        return true;
                    }
                }
            } else {
                return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
            }
            return false;
        }
    }
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary = new WordDictionary();
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");
    

  • 0
    V

    What is the complexity of this?


  • 1

    Similar solution, but with Map for unicode support and simpler code:

    public class WordDictionary {
      private final Node root = new Node();
    
      public void addWord(String word) {
        Node node = root;
        for (char c : word.toCharArray())
          node = node.children.computeIfAbsent(c, k -> new Node());
        node.terminal = word;
      }
    
      public boolean search(String word) {
        Deque<Node> level = new ArrayDeque<>(Arrays.asList(root));
        for (char c : word.toCharArray())
          for (int i = level.size(); i > 0; i--) {
            Map<Character, Node> children = level.removeFirst().children;
            switch (c) {
              case '.': level.addAll(children.values()); break;
              default: if (children.containsKey(c)) level.addLast(children.get(c)); break;
            }
          }
        return level.stream().anyMatch(n -> n.terminal != null);
      }
    
      private class Node {
        public Map<Character, Node> children = new HashMap<>();
        public String terminal;
      }
    }
    

    Complexity analysis: if you have e.g. ["aaaaa", "aaaab", "aaaac"] and search for "....." it will index all the words (linear to the number of total characters).

    If you exclude wildcards (.), worst-case-search will iterate through the longest word (i.e. linear to the maximum number of characters in a word).

    With wildcards it will iterate through the whole tree in the worst case (see above), making it the same complexity as the indexing.


  • 0
    D

    similar idea using trie, use recursion to build trie and search word

    public class WordDictionary {
    
        // trie
        class Node
        {
            // if end is true, means from root to current Node, form a word
            boolean end;
            Node[] next;
            
            Node()
            {
                end = false;
                next = new Node[26];
            }
        }
        
        Node root;
        /** Initialize your data structure here. */
        public WordDictionary() {
            root = new Node();
        }
        
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            addChar(root, word.toCharArray(), 0);
        }
        
        private void addChar(Node n, char[] s, int id)
        {
            if (id == s.length) 
            {
                n.end = true;
                return; 
            }
            
            if (n.next[s[id] - 'a'] == null)
            {
                n.next[s[id] - 'a'] = new Node();
            }
            
            addChar(n.next[s[id] - 'a'], s, id + 1);
        }
        
        /** 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 dfs(root, word.toCharArray(), 0);
        }
        
        private boolean dfs(Node n, char[] s, int id)
        {
            if (n == null) { return false; }
            if (id == s.length) { return n.end; }
            
            boolean find = false;
            if (s[id] == '.')
            {
                // go all possible ways
                for (int i = 0; i < 26; i++)
                {
                    find |= dfs(n.next[i], s, id + 1);
                }
            }
            else
            {
                int pos = s[id] - 'a';
                find = dfs(n.next[pos], s, id + 1);
            }
            
            return find;
        }
    }
    

  • 0
    Q

    @paplorinc impressive coding with JDK8's new features!


  • 1
    R

    C#, same Idea..

    public class WordDictionary {
    
        /** Initialize your data structure here. */
        public class TrieNode
        {
            public Dictionary<char, TrieNode> map;
            public bool endOfWord;
            public TrieNode()
            {
                map = new Dictionary<char, TrieNode>();
            }
        }
        
        TrieNode root;
        public WordDictionary() {
           root = new TrieNode();
        }
        
        /** Adds a word into the data structure. */
        public void AddWord(string word) {
            TrieNode curr = root;
            for(int i=0; i<word.Length; i++)
            {
                TrieNode node;
                if(curr.map.ContainsKey(word[i]))
                {
                    node = curr.map[word[i]];
                }
                else
                {
                    node = new TrieNode();
                    curr.map.Add(word[i], node);
                }
                
                curr = node;
            }
            
            curr.endOfWord = true;
        }
        
        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
        public bool Search(string word) {
            return Search(word, root, 0);
        }
        
        
        public bool Search(string word, TrieNode node, int wordIndex)
        {
            if(wordIndex == word.Length) 
            {
                if(node.endOfWord == true)
                    return true;
                else 
                    return false;
            }
        
            TrieNode curr = node;
            char ch = word[wordIndex];
            if(curr.map.ContainsKey(ch))
            {
                curr = curr.map[ch];
                if(Search(word, curr, wordIndex+1)) return true;
            }
            else if(ch == '.')
            {
                foreach(char c in curr.map.Keys)
                {
                    if(Search(word, curr.map[c], wordIndex+1)) return true;
                }
            }
            
            return false;
        }
    }
    
    /**
     * Your WordDictionary object will be instantiated and called as such:
     * WordDictionary obj = new WordDictionary();
     * obj.AddWord(word);
     * bool param_2 = obj.Search(word);
     */
    

  • 0
    A

    @Lnic I liked your solution. I just have a question, If word is "b.." and in trie it is "bata", should it match or not? If not, will the solution work?


  • 1
    F

    Here is my code, however, it could not pass this test. the 6th and 8th search queries are exactly the same, why should it even expect to have different result?

    Below is the test Case I failed, notice the 6th and 8th queries, they are both "[.at]", but the first one returns false and the other returns false ):

    Input:
    ["WordDictionary","addWord","addWord","addWord","addWord","search","search","addWord","search","search","search","search","search","search"]
    [[],["at"],["and"],["an"],["add"],["a"],[".at"],["bat"],[".at"],["an."],["a.d."],["b."],["a.d"],["."]]
    
    Output:
    [null,null,null,null,null,false,false,null,false,true,false,false,true,false]
    
    Expected:
    [null,null,null,null,null,false,false,null,true,true,false,false,true,false]
    
    class TrieNode {
        public char val;
        public TrieNode[] children = new TrieNode[26]; // notice this
        public boolean isWord = false;
        public TrieNode() {}
        public TrieNode(char c) {
            this.val = c;
        }
    }
        
    public class WordDictionary {
    
        private TrieNode root;
    
        /** Initialize your data structure here. */
        public WordDictionary() {
             root = new TrieNode();
        }
    
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            TrieNode currentNode = root;
            for (int i = 0; i < word.length(); i++) {
                char currentChar = Character.toLowerCase(word.charAt(i));
                if (currentNode.children[currentChar - 'a'] == null) {
                    currentNode.children[currentChar - 'a'] = new TrieNode(currentChar);
                }
                currentNode = currentNode.children[currentChar - 'a'];
            }
            currentNode.isWord = true;
        }
    
        /** 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);
        }
        
        // backtrack
        private boolean search(String word, int index, TrieNode currentNode) {
            if (index == word.length()) {
                return currentNode.isWord;
            }
            if (word.charAt(index) != '.') {
                if (currentNode.children[word.charAt(index) - 'a'] != null) {
                    return search(word, index+1, currentNode.children[word.charAt(index) - 'a']);
                }
            } else {
                for (int i = 0; i < currentNode.children.length; i++) {
                    if (currentNode.children[i] != null) {
                        return search(word, index+1, currentNode.children[i]);
                    }
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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