@Yano 2019-09-20T10:55:54.000000Z 字数 2127 阅读 4898

# LeetCode之Trie题目汇总

LeetCode

# 公众号

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

https://github.com/LjyYano/Thinking_in_Java_MindMapping

LeetCode 题目汇总

# Implement Trie (Prefix Tree)

Implement a trie with insertsearch, 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");

• 私有
• 公开
• 删除