LeetCode之Trie题目汇总

LeetCode

公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

文章目录：

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

    class TrieNode {
        boolean isLeaf;
        char c;
        HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
        // Initialize your data structure here.
        public TrieNode() {
        }
        public TrieNode(char c) {
            this.c = c;
        }
    }
    public class Trie {
        private TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        // Inserts a word into the trie.
        public void insert(String word) {
            HashMap<Character, TrieNode> children = root.children;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                TrieNode t;
                if (children.containsKey(c)) {
                    t = children.get(c);
                } else {
                    t = new TrieNode(c);
                    children.put(c, t);
                }
                children = t.children;
                if (i == word.length() - 1) {
                    t.isLeaf = true;
                }
            }
        }
        // Returns if the word is in the trie.
        public boolean search(String word) {
            HashMap<Character, TrieNode> children = root.children;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!children.containsKey(c)) {
                    return false;
                }
                if (i == word.length() - 1) {
                    if (children.get(c).isLeaf == true) {
                        return true;
                    }
                    return false;
                }
                children = children.get(c).children;
            }
            // useless
            return false;
        }
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            HashMap<Character, TrieNode> children = root.children;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if (!children.containsKey(c)) {
                    return false;
                }
                if (i == prefix.length() - 1) {
                    return true;
                }
                children = children.get(c).children;
            }
            // useless
            return false;
        }
    }
    // Your Trie object will be instantiated and called as such:
    // Trie trie = new Trie();
    // trie.insert("somestring");
    // trie.search("key");