leetcode 208. 实现 Trie (前缀树)

淡淡的烟草味﹌ 2022-02-22 01:41 245阅读 0赞

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();
    
    trie.insert("apple");
    trie.search("apple");   // 返回 true
    trie.search("app");     // 返回 false
    trie.startsWith("app"); // 返回 true
    trie.insert("app");   
    trie.search("app");     // 返回 true

**说明:**

*  你可以假设所有的输入都是由小写字母 a-z 构成的。
 *  保证所有输入均为非空字符串。

**思路:**  
Trie的基本实现,两种解题方法,一种是递归实现,一种是迭代实现  
递归实现:

package Trie;
    
    import java.util.TreeMap;
    
    // leetcode 208. 实现 Trie (前缀树)
    class Trie { 
    
        private class Node { 
            public boolean isWord;
            public TreeMap<Character, Node> next;
    
            public Node(boolean isWord) { 
                this.isWord = isWord;
                next = new TreeMap<>();
            }
    
            public Node() { 
                this(false);
            }
        }
    
        private Node root;
    
    
        /** Initialize your data structure here. */
        public Trie() { 
            root = new Node();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) { 
            Node cur = root;
            add(root, word, 0);
        }
    
        public void add(Node node, String word, int index) { 
            // 此时一个单词已经遍历完成了,如果这个结束节点没有标记为单词,就标记为单词
            if (!node.isWord && index == word.length()) { 
                node.isWord = true;
            }
    
            if (word.length() > index) { 
                char addLetter = word.charAt(index);
                if (node.next.get(addLetter) == null) { 
                    node.next.put(addLetter, new Node());
                }
                add(node.next.get(addLetter), word, index + 1);
            }
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) { 
            Node cur = root;
            return contains(root, word, 0);
        }
    
        private boolean contains(Node node, String word, int index) { 
            if (index == word.length()) { 
                return node.isWord;
            }
            char c = word.charAt(index);
            if (node.next.get(c) == null) { 
                return false;
            } else { 
                return contains(node.next.get(c), word, index + 1);
            }
        }
    
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) { 
            Node node = root;
            return recursionIsPrefix(root, prefix, 0);
        }
    
        public boolean recursionIsPrefix(Node root, String prefix, int index) { 
            if(prefix.length() == index) { 
                return true;
            }
            char c = prefix.charAt(index);
            if(root.next.get(c) == null) { 
                return false;
            } else { 
                return recursionIsPrefix(root.next.get(c), prefix, ++index);
            }
        }
    
    }
    
    /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

**迭代实现:**

package Trie;
    
    import java.util.TreeMap;
    
    // leetcode 208. 实现 Trie (前缀树)
    class Trie2 { 
    
        private class Node { 
            public boolean isWord;
            public TreeMap<Character, Node> next;
    
            public Node(boolean isWord) { 
                this.isWord = isWord;
                next = new TreeMap<>();
            }
    
            public Node() { 
                this(false);
            }
        }
    
        private Node root;
    
    
        /** Initialize your data structure here. */
        public Trie2() { 
            root = new Node();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) { 
            Node cur = root;
            // 取字符串中的字符,在树上进行查询,无则添加,有则下一个
            for (int i = 0; i < word.length(); i++) { 
                char c = word.charAt(i);
                if (cur.next.get(c) == null) { 
                    cur.next.put(c, new Node());
                }
                cur = cur.next.get(c);
            }
            // 此时一个单词已经遍历完成了,如果这个结束节点没有标记为单词,就标记为单词
            if (!cur.isWord) { 
                cur.isWord = true;
            }
        }
    
    
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) { 
            Node cur = root;
            for (int i = 0; i < word.length(); i++) { 
                char c = word.charAt(i);
                if (cur.next.get(c) == null) { 
                    return false;
                } else { 
                    cur = cur.next.get(c);
                }
            }
            return cur.isWord;
        }
    
    
    
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) { 
            Node cur = root;
            for (int i = 0; i < prefix.length(); i++) { 
                char c = prefix.charAt(i);
                if(cur.next.get(c) == null) { 
                    return false;
                }
                cur = cur.next.get(c);
            }
            return true;
        }
    
    
    }
    
    /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */