Question

Formatted question description: https://leetcode.ca/all/208.html

208	Implement Trie (Prefix Tree)

Implement a trie with methods
    insert
    search
    startsWith

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

@tag-trie

Algorithm

Each node of the alphabetic dictionary tree defines an array of child node pointers with a size of 26, and then uses a marker to record whether it is a word up to the current position.

When initializing, the 26 child nodes are all empty.

Then the insert() operation only needs to calculate the position of each character of the string to be inserted, and then find out whether this child node exists, if it does not exist, create a new one, and then move to the next one.

The word search() and prefix search operations are very similar to the insert operation. The difference is that if there are no child nodes, false is returned. At the end of the search time, you need to look at the flag, and you can directly return true when you search the prefix.

Code

Java

public class Implement_Trie_Prefix_Tree {

    public static void main(String[] args) {
        Implement_Trie_Prefix_Tree out = new Implement_Trie_Prefix_Tree();

        Trie trie = out.new Trie();
        trie.insert("abc");
        trie.insert("ab");
        System.out.println(trie.search("ab"));
        trie.insert("ab");
        System.out.println(trie.search("ab"));
        System.out.println(trie.startsWith("a"));

    }

    class TrieNode {

        // R children to node children
        private TrieNode[] children;

        private final int R = 26;

        private boolean isEnd;

        public TrieNode() {
            children = new TrieNode[R];
        }

        public boolean containsKey(char ch) {
            return children[ch - 'a'] != null;
        }

        public TrieNode get(char ch) {
            return children[ch - 'a'];
        }

        public void put(char ch, TrieNode node) {
            children[ch - 'a'] = node;
        }

        public void setEnd() {
            isEnd = true;
        }

        public boolean isEnd() {
            return isEnd;
        }
    }

    class Trie {
        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        // Inserts a word into the trie.
        public void insert(String word) {
            TrieNode node = root;

            // @note:@memorize: iteration is better than recursion during trie building
            for (int i = 0; i < word.length(); i++) {
                char currentChar = word.charAt(i);
                if (!node.containsKey(currentChar)) {
                    node.put(currentChar, new TrieNode());
                }
                node = node.get(currentChar);
            }
            node.setEnd();
        }

        // search a prefix or whole key in trie and
        // returns the node where search ends
        private TrieNode searchPrefix(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char curLetter = word.charAt(i);
                if (node.containsKey(curLetter)) {
                    node = node.get(curLetter);
                } else {
                    return null;
                }
            }
            return node;
        }

        // Returns if the word is in the trie.
        public boolean search(String word) {
            TrieNode node = searchPrefix(word);
            return node != null && node.isEnd();
        }

        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            TrieNode node = searchPrefix(prefix);
            return node != null;
        }
    }

    // Your Trie object will be instantiated and called as such:
    // Trie trie = new Trie();
    // trie.insert("somestring");
    // trie.search("key");

}

// OJ: https://leetcode.com/problems/implement-trie-prefix-tree/
// Time: O(W) for insert/search/startsWith
// Space: O(1) extra space for all
struct TrieNode {
    TrieNode *next[26] = {};
    bool word = false;
};
class Trie {
    TrieNode root;
    TrieNode *find(string &word) {
        auto node = &root;
        for (char c : word) {
            if (!node->next[c - 'a']) return NULL;
            node = node->next[c - 'a'];
        }
        return node;
    }
public:
    void insert(string word) {
        auto node = &root;
        for (char c : word) {
            if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
            node = node->next[c - 'a'];
        }
        node->word = true;
    }
    bool search(string word) {
        auto node = find(word);
        return node && node->word;
    }
    bool startsWith(string prefix) {
        return find(prefix);
    }
};

import collections

class TrieNode:

	def __init__(self):
		'''
			Usually, a Python dictionary throws a KeyError if you try to get an item with a key that is not currently in the dictionary.
			The defaultdict in contrast will simply create any items that you try to access

			https://stackoverflow.com/questions/5900578/how-does-collections-defaultdict-work
		'''
		self.child = collections.defaultdict(TrieNode)
		self.is_word = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word: str) -> None:
		cur = self.root
		for letter in word:
			cur = cur.child[letter]
		cur.is_word = True

	def search(self, word: str) -> bool:
		cur = self.root
		for letter in word:
			# cur = cur.child[letter] ==> will not work, it will creat a default node for this letter
			cur = cur.child.get(letter)
			if not cur:
				return False
		return cur.is_word

	def startsWith(self, prefix: str) -> bool:
		cur = self.root
		for letter in prefix:
			# cur = cur.child[letter] ==> will not work, it will creat a default node for this letter
			cur = cur.child.get(letter)
			if not cur:
				return False
		return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)



# below is using reduce()
class Trie(object):

    def __init__(self):
        T = lambda: collections.defaultdict(T)
        self.root = T()

    def insert(self, word):
        reduce(dict.__getitem__, word, self.root)['#'] = True

    def search(self, word):
        return '#' in reduce(lambda cur, c: cur.get(c, {}), word, self.root)

    def startsWith(self, prefix):
        return bool(reduce(lambda cur, c: cur.get(c, {}), prefix, self.root))

208 - Implement Trie (Prefix Tree)

Question

Algorithm

Code

All Problems

All Solutions