208. Implement Trie (Prefix Tree) – Leetcode Solutions

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

class TrieNode:
    def __init__(self):
        # Each TrieNode contains a dictionary that maps characters to their child nodes
        self.children = {}
        # A boolean flag that marks whether a node corresponds to the end of a valid word
        self.is_end_of_word = False

class Trie:

    def __init__(self):
        # The Trie itself contains only one root node, which is an instance of TrieNode
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for char in word:
            # For each character in the word, if the character is not present in the current node's
            # children, add a new node for this character.
            if char not in node.children:
                node.children[char] = TrieNode()
            # Move to the child node corresponding to the character
            node = node.children[char]
        # After inserting all characters, mark the end of the word
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        """
        Returns True if the word is in the trie, and False otherwise.
        """
        node = self.root
        for char in word:
            # Traverse through the Trie, moving to the child node that corresponds to the character
            if char not in node.children:
                return False  # If a character is not found, the word does not exist in the Trie
            node = node.children[char]
        # After traversing all characters, check if this node marks the end of a valid word
        return node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        """
        Returns True if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for char in prefix:
            # Traverse through the Trie, moving to the child node that corresponds to the character
            if char not in node.children:
                return False  # If a character is not found, no word starts with this prefix
            node = node.children[char]
        # If we can traverse through the entire prefix, return True
        return True

// Define a TrieNode class that represents each node in the Trie
class TrieNode {
    constructor() {
        // Each TrieNode contains a map of children nodes
        this.children = {};
        // A boolean flag to mark if this node represents the end of a word
        this.isEndOfWord = false;
    }
}

// Define the Trie class
var Trie = function() {
    // Initialize the Trie with a root node which is an instance of TrieNode
    this.root = new TrieNode();
};

/** 
 * Inserts a word into the Trie.
 * @param {string} word - The word to be inserted
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let node = this.root;
    // Iterate through each character of the word
    for (let char of word) {
        // If the character is not in the current node's children, add it
        if (!node.children[char]) {
            node.children[char] = new TrieNode();
        }
        // Move to the child node corresponding to the character
        node = node.children[char];
    }
    // After inserting all characters, mark the end of the word
    node.isEndOfWord = true;
};

/** 
 * Searches for a word in the Trie.
 * @param {string} word - The word to be searched
 * @return {boolean} - True if the word exists in the Trie, false otherwise
 */
Trie.prototype.search = function(word) {
    let node = this.root;
    // Iterate through each character of the word
    for (let char of word) {
        // If the character is not in the current node's children, the word is not present
        if (!node.children[char]) {
            return false;
        }
        // Move to the child node corresponding to the character
        node = node.children[char];
    }
    // After traversing all characters, check if this node marks the end of a valid word
    return node.isEndOfWord;
};

/** 
 * Checks if there is any word in the Trie that starts with the given prefix.
 * @param {string} prefix - The prefix to be checked
 * @return {boolean} - True if there is a word starting with the prefix, false otherwise
 */
Trie.prototype.startsWith = function(prefix) {
    let node = this.root;
    // Iterate through each character of the prefix
    for (let char of prefix) {
        // If the character is not in the current node's children, no word starts with this prefix
        if (!node.children[char]) {
            return false;
        }
        // Move to the child node corresponding to the character
        node = node.children[char];
    }
    // If we can traverse the entire prefix, then there is at least one word with this prefix
    return true;
};

import java.util.HashMap;
import java.util.Map;

// Define a TrieNode class that represents each node in the Trie
class TrieNode {
    // Each TrieNode contains a map of children nodes
    Map<Character, TrieNode> children;
    // A boolean flag to mark if this node represents the end of a word
    boolean isEndOfWord;

    // Constructor to initialize the TrieNode
    public TrieNode() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
    }
}

// Define the Trie class
class Trie {

    private TrieNode root;

    // Constructor to initialize the Trie with a root node
    public Trie() {
        this.root = new TrieNode();
    }

    /** 
     * Inserts a word into the Trie.
     * @param word - The word to be inserted
     */
    public void insert(String word) {
        TrieNode node = root;
        // Iterate through each character of the word
        for (char ch : word.toCharArray()) {
            // If the character is not present in the current node's children, add it
            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new TrieNode());
            }
            // Move to the child node corresponding to the character
            node = node.children.get(ch);
        }
        // After inserting all characters, mark the end of the word
        node.isEndOfWord = true;
    }

    /** 
     * Searches for a word in the Trie.
     * @param word - The word to be searched
     * @return true if the word exists in the Trie, false otherwise
     */
    public boolean search(String word) {
        TrieNode node = root;
        // Iterate through each character of the word
        for (char ch : word.toCharArray()) {
            // If the character is not present in the current node's children, the word is not present
            if (!node.children.containsKey(ch)) {
                return false;
            }
            // Move to the child node corresponding to the character
            node = node.children.get(ch);
        }
        // After traversing all characters, check if this node marks the end of a valid word
        return node.isEndOfWord;
    }

    /** 
     * Checks if there is any word in the Trie that starts with the given prefix.
     * @param prefix - The prefix to be checked
     * @return true if there is a word starting with the prefix, false otherwise
     */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        // Iterate through each character of the prefix
        for (char ch : prefix.toCharArray()) {
            // If the character is not present in the current node's children, no word starts with this prefix
            if (!node.children.containsKey(ch)) {
                return false;
            }
            // Move to the child node corresponding to the character
            node = node.children.get(ch);
        }
        // If we can traverse the entire prefix, then there is at least one word with this prefix
        return true;
    }
}

using System.Collections.Generic;

public class TrieNode
{
    // A dictionary to hold children nodes
    public Dictionary<char, TrieNode> Children { get; private set; }
    // A boolean flag to mark the end of a word
    public bool IsEndOfWord { get; set; }

    // Constructor to initialize the TrieNode
    public TrieNode()
    {
        Children = new Dictionary<char, TrieNode>();
        IsEndOfWord = false;
    }
}

public class Trie
{
    // The root node of the Trie
    private TrieNode root;

    // Constructor to initialize the Trie with a root node
    public Trie()
    {
        root = new TrieNode();
    }

    /** 
     * Inserts a word into the Trie.
     * @param word - The word to be inserted
     */
    public void Insert(string word)
    {
        TrieNode node = root;
        // Iterate through each character of the word
        foreach (char ch in word)
        {
            // If the character is not present in the current node's children, add it
            if (!node.Children.ContainsKey(ch))
            {
                node.Children[ch] = new TrieNode();
            }
            // Move to the child node corresponding to the character
            node = node.Children[ch];
        }
        // After inserting all characters, mark the end of the word
        node.IsEndOfWord = true;
    }

    /** 
     * Searches for a word in the Trie.
     * @param word - The word to be searched
     * @return true if the word exists in the Trie, false otherwise
     */
    public bool Search(string word)
    {
        TrieNode node = root;
        // Iterate through each character of the word
        foreach (char ch in word)
        {
            // If the character is not present in the current node's children, the word is not present
            if (!node.Children.ContainsKey(ch))
            {
                return false;
            }
            // Move to the child node corresponding to the character
            node = node.Children[ch];
        }
        // After traversing all characters, check if this node marks the end of a valid word
        return node.IsEndOfWord;
    }

    /** 
     * Checks if there is any word in the Trie that starts with the given prefix.
     * @param prefix - The prefix to be checked
     * @return true if there is a word starting with the prefix, false otherwise
     */
    public bool StartsWith(string prefix)
    {
        TrieNode node = root;
        // Iterate through each character of the prefix
        foreach (char ch in prefix)
        {
            // If the character is not present in the current node's children, no word starts with this prefix
            if (!node.Children.ContainsKey(ch))
            {
                return false;
            }
            // Move to the child node corresponding to the character
            node = node.Children[ch];
        }
        // If we can traverse the entire prefix, then there is at least one word with this prefix
        return true;
    }
}