Simple Trie in Java

  • 0

    A few things about Trie may help to understand it better:

    1. A trie node maintains a map of character and another TrieNode.
    2. It will be easier to keep a root node and do everything relative to it.
    3. A trie node represents all mappings to a single character without adding that character explicitly. We also use an empty trie node with isend=true to mark the end of the word. For example, to add the word "bad", here is what happens:

    root "b"-> TrieNode of "a"
    "a" --> TrieNode of "d"
    "d" -> TrieNode of isEnd=true.

    public class WordDictionary {
        private final TrieNode root = new TrieNode();
        /** Adds a word into the data structure. */
        public void addWord(String 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) {
        private class TrieNode {
            private final Map<Character,TrieNode> map = new HashMap<>();
            private boolean isEnd;
            void add(String s, int pos) {
                if(pos==s.length()) {
                TrieNode node = map.get(s.charAt(pos));
                if(node==null) {
                    node = new TrieNode();
            boolean search(String s, int pos) {
                if(pos == s.length()) {
                    return isEnd;
                char c = s.charAt(pos);
                if(c=='.') {
                    //dfs for all values.
                    for(TrieNode n : map.values()) {
                        if(,pos+1)) {
                            return true;
                    return false;
                TrieNode node = map.get(s.charAt(pos));
                if(node == null) {
                    return false;

Log in to reply

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