DevExCode

LeetCode 208: Implement Trie (Prefix Tree)

Hash TableStringDesignTrie

Problem Description

Explanation

A Trie, also known as a Prefix Tree, is a tree-like data structure used to store a dynamic set of strings. Each node in the Trie represents a single character. By following the path from the root to a particular node, we can reconstruct the string formed by the characters along that path.

For this problem, we need to implement a Trie class with the following functionalities:

  1. Trie() - Initialize the Trie data structure.
  2. insert(String word) - Insert a word into the Trie.
  3. search(String word) - Check if a word exists in the Trie.
  4. startsWith(String prefix) - Check if any word in the Trie starts with a given prefix.

To implement these functionalities, we can use a TrieNode class to represent each node in the Trie. Each TrieNode will have a map to store references to its children nodes. The root of the Trie corresponds to an empty string, and each character in the word corresponds to a level in the Trie.

Time Complexity

  • Insertion: O(m), where m is the length of the word being inserted.
  • Search: O(m), where m is the length of the word being searched.
  • StartsWith: O(m), where m is the length of the prefix being checked.

Space Complexity

  • O(n*m), where n is the number of words inserted and m is the average length of the words.
View on LeetCode

Solutions

class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (!node.containsKey(c)) {
                node.put(c, new TrieNode());
            }
            node = node.get(c);
        }
        node.setEnd();
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.containsKey(c)) {
                node = node.get(c);
            } else {
                return null;
            }
        }
        return node;
    }

    class TrieNode {
        private TrieNode[] links;
        private final int R = 26;
        private boolean isEnd;

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

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

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

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

        public void setEnd() {
            isEnd = true;
        }

        public boolean isEnd() {
            return isEnd;
        }
    }
}

Related LeetCode Problems

Previous ProblemNext Problem

Loading editor...