Implement Trie Prefix Tree

                                            
class Trie {
    private TrieNode root;

    private static class TrieNode {
        TrieNode[] children;
        boolean isEnd;

        TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node != null;
    }
}

                                            
class Trie(object):
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node['$'] = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return '$' in node

    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

                                            
typedef struct {
    bool isEnd;
    struct Trie* children[26];
} Trie;

/** Initialize your data structure here. */

Trie* trieCreate() {
    Trie* node = (Trie*)malloc(sizeof(Trie));
    node->isEnd = false;
    for (int i = 0; i < 26; i++) {
        node->children[i] = NULL;
    }
    return node;
}

/** Inserts a word into the trie. */
void trieInsert(Trie* obj, char * word) {
    Trie* curr = obj;
    while (*word) {
        int index = *word - 'a';
        if (curr->children[index] == NULL) {
            curr->children[index] = trieCreate();
        }
        curr = curr->children[index];
        word++;
    }
    curr->isEnd = true;
}

/** Returns if the word is in the trie. */
bool trieSearch(Trie* obj, char * word) {
    Trie* curr = obj;
    while (*word) {
        int index = *word - 'a';
        if (curr->children[index] == NULL) {
            return false;
        }
        curr = curr->children[index];
        word++;
    }
    return curr != NULL && curr->isEnd;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool trieStartsWith(Trie* obj, char * prefix) {
    Trie* curr = obj;
    while (*prefix) {
        int index = *prefix - 'a';
        if (curr->children[index] == NULL) {
            return false;
        }
        curr = curr->children[index];
        prefix++;
    }
    return curr != NULL;
}

void trieFree(Trie* obj) {
    if (obj == NULL) {
        return;
    }
    for (int i = 0; i < 26; i++) {
        trieFree(obj->children[i]);
    }
    free(obj);
}

                                            
public class Trie {
    private TrieNode root;

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

    public void Insert(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            if (!node.Contains(c)) {
                node.Add(c);
            }
            node = node.Get(c);
        }
        node.IsEnd = true;
    }

    public bool Search(string word) {
        TrieNode node = SearchPrefix(word);
        return node != null && node.IsEnd;
    }

    public bool StartsWith(string prefix) {
        TrieNode node = SearchPrefix(prefix);
        return node != null;
    }

    private TrieNode SearchPrefix(string prefix) {
        TrieNode node = root;
        foreach (char c in prefix) {
            if (node.Contains(c)) {
                node = node.Get(c);
            } else {
                return null;
            }
        }
        return node;
    }

    private class TrieNode {
        private TrieNode[] links;
        public bool IsEnd;

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

        public bool Contains(char c) {
            return links[c - 'a'] != null;
        }

        public void Add(char c) {
            links[c - 'a'] = new TrieNode();
        }

        public TrieNode Get(char c) {
            return links[c - 'a'];
        }
    }
}

                                            
var Trie = function() {
    this.root = {};
    
    this.insert = function(word) {
        let node = this.root;
        for (let char of word) {
            if (!node[char]) {
                node[char] = {};
            }
            node = node[char];
        }
        node.isEnd = true;
    };
    
    this.search = function(word) {
        let node = this.root;
        for (let char of word) {
            if (!node[char]) {
                return false;
            }
            node = node[char];
        }
        return node.isEnd === true;
    };
    
    this.startsWith = function(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node[char]) {
                return false;
            }
            node = node[char];
        }
        return true;
    };
};

                                            
class Trie {
    private $children = [];
    private $isEndOfWord = false;
    
    function __construct() {
    }
    
    function insert($word) {
        $current = $this;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($current->children[$char])) {
                $current->children[$char] = new Trie();
            }
            $current = $current->children[$char];
        }
        $current->isEndOfWord = true;
    }

    function search($word) {
        $current = $this;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($current->children[$char])) {
                return false;
            }
            $current = $current->children[$char];
        }
        return ($current != null && $current->isEndOfWord);
    }

    function startsWith($prefix) {
        $current = $this;
        for ($i = 0; $i < strlen($prefix); $i++) {
            $char = $prefix[$i];
            if (!isset($current->children[$char])) {
                return false;
            }
            $current = $current->children[$char];
        }
        return true;
    }
}

To solve this coding challenge of implementing a Trie (Prefix Tree), we need to create the Trie data structure which is useful for efficient storage and retrieval of strings. Below, we provide a detailed methodology on how to implement the Trie class with the required methods, followed by pseudocode with comments for clarity.

# Explanation

The Trie data structure is essentially a tree where each node represents a single character of a string. It has the following main operations:

Insert : This method involves adding a new word to the Trie. We iterate through each character in the word and create a corresponding node in the Trie if it doesn't already exist.
Search : This method checks if a given word exists in the Trie. We traverse the Trie nodes corresponding to each character of the word to see if they exist and if the word terminates properly at the end.
StartsWith : This method checks if any word in the Trie starts with the given prefix. We traverse the Trie nodes corresponding to each character of the prefix to see if they exist.

Here's a detailed step-by-step explanation and corresponding pseudocode for each method:

Step-by-Step Explanation

Initialization of the Trie (Constructor) :

We initialize the Trie with an empty root dictionary. This root serves as the starting point for all inserted words. Each node in the Trie will also be represented by a dictionary.

Insert Method :

We start with the root node. For each character in the word to be inserted:

Check if the character is already a child of the current node.
If not, create a new node (an empty dictionary) for this character.
Move to the corresponding node for this character.

After processing all characters, mark the end of the word by inserting a special marker (e.g.,
$

) in the final node.

Search Method :

We start with the root node. For each character in the word to be searched:

Check if the character is a child of the current node.
If not, return
False

as the word doesn't exist in the Trie.
Move to the corresponding node for this character.

After processing all characters, check for the special marker to confirm the end of the word. Return
True

if the marker exists, otherwise
False

.

StartsWith Method :

We start with the root node. For each character in the prefix:

Check if the character is a child of the current node.
If not, return
False

as no word in the Trie starts with this prefix.
Move to the corresponding node for this character.

If all characters of the prefix are found in sequence, return
True

.

Detailed Steps in Pseudocode

Initialization of the Trie (Constructor)

                                            
# Initialize root of Trie as an empty dictionary
Class Trie:
    Method __init__:
        Initialize root as an empty dictionary {}

Insert Method

                                            
Method insert(word):
    # Start from the root node
    Assign node to root
    
    # Traverse each character in the word
    For each character in word:
        If character is not in node: 
            # Create a new node for this character
            node[character] = {}
        # Move to the next node
        node = node[char]
    
    # Mark the end of the word with special character
    node['$'] = True

Search Method

                                            
Method search(word):
    # Start from the root node
    Assign node to root
    
    # Traverse each character in the word
    For each character in word:
        If character is not in node:
            # If character not found, word does not exist
            Return False
        # Move to the next node
        node = node[char]
    
    # Check end of word marker
    Return '$' in node

StartsWith Method

                                            
Method startsWith(prefix):
    # Start from the root node
    Assign node to root
    
    # Traverse each character in the prefix
    For each character in prefix:
        If character is not in node:
            # If character not found, prefix does not exist
            Return False
        # Move to the next node
        node = node[char]
    
    # All characters found, prefix exists
    Return True

By following these steps and using the provided pseudocode, you will be able to implement a complete Trie data structure that supports insertions, searches, and prefix checks efficiently.