My simple and clean Java code


  • 55
    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;
        }
    }

  • -3
    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.


  • 25
    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!


  • 0
    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?


Log in to reply
 

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