Leetcode Implement Trie (Prefix Tree) problem solution

In this Leetcode Implement Trie (Prefix Tree) problem solution, A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if a previously inserted string word has the prefix, and false otherwise.

Leetcode Implement Trie (Prefix Tree) problem solution

Topics we are covering

Problem solution in Python.

class Trie(defaultdict):
  def __init__(self):
    self.full = self.count = 0
    super().__init__(Trie)

  def insert(self, word: str) -> None:
    for c in word: (self := self[c]).count += 1
    self.full = 1

  def search(self, word: str) -> bool:
    return reduce(getitem, word, self).full == 1

  def startsWith(self, prefix: str) -> bool:
    return reduce(getitem, prefix, self).count > 0

Problem solution in Java.

class Trie {
    public class Node{
        char c;
        boolean isWord;
        Node[] children;
        public Node(char c){
            this.c = c;
            this.children = new Node[26];
            this.isWord = false;
        }
    }
    Node root;
    public Trie() {
        root  = new Node('');
    }
    public void insert(String word) {
        Node curr = root;
        for(int i =0;i<word.length();i++){
            char cc = word.charAt(i);
            if(curr.children[cc-'a'] == null) curr.children[cc-'a'] = new Node(cc);
            curr = curr.children[cc-'a'];
        }
        curr.isWord = true;
    }

    public boolean search(String word) {
        Node curr = root;
        for(int i = 0;i<word.length();i++){
            char cc = word.charAt(i);
            if(curr.children[cc-'a'] == null) return false;
            curr = curr.children[cc-'a'];
        }
        return curr.isWord == true?true:false;
    }

    public boolean startsWith(String word) {
        Node curr = root;
        for(int i = 0;i<word.length();i++){
            char cc = word.charAt(i);
            if(curr.children[cc-'a'] == null) return false;
            curr = curr.children[cc-'a'];
        }
        return true;
    }
}

Problem solution in C++.

class TrieNode {
public:
    TrieNode() {
        
    }
    TrieNode *children[26] = {NULL};
    bool isNode = false;
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    void insert(string word) {
        TrieNode *current = root;
        for (auto c : word) {
            int index = c - 'a';
            if (current->children[index] == NULL) {
                current->children[index] = new TrieNode();
            }
            current = current->children[index];
        }
        current->isNode = 1;
    }
    
    bool search(string &word, bool isPrefix) {
        TrieNode *current = root;
        for (auto c : word) {
            int index = c - 'a';
            if (current->children[index] == NULL)
                return false;
            current = current->children[index];
        }
        return isPrefix || current->isNode; 
    }
    bool search(string word) {
        return search(word, false);
    }
    bool startsWith(string prefix) {
        return search(prefix, true);
    }

private:
    TrieNode* root;
};

Problem solution in C.

int size = 26;

typedef struct 
{
	struct Trie* childs[26];
	bool isEndOfWord;
} Trie;

Trie* trieCreate()
{
	Trie* node = malloc(sizeof(Trie));
	node->isEndOfWord = false;

	for (int i = 0; i < size; i++)
	{
		node->childs[i] = NULL;
	}

	return node;
}

void trieInsert(Trie* obj, char * word) 
{
	Trie* crawler = obj;
	int len = strlen(word);

	for (int i = 0; i < len; i++)
	{
		int index = word[i] - 'a';
		if (crawler->childs[index] == NULL)
		{
			crawler->childs[index] = trieCreate();
		}

		crawler = crawler->childs[index];
	}

	crawler->isEndOfWord = true;
}

bool trieSearch(Trie* obj, char * word) 
{
	Trie* crawler = obj;
	int len = strlen(word);

	for (int i = 0; i < len; i++)
	{
		int index = word[i] - 'a';
		if (crawler->childs[index] == NULL)
		{
			return false;
		}

		crawler = crawler->childs[index];
	}

	return crawler->isEndOfWord;
}

bool trieStartsWith(Trie* obj, char * prefix)
{
	Trie* crawler = obj;
	int len = strlen(prefix);

	for (int i = 0; i < len; i++)
	{
		int index = prefix[i] - 'a';
		if (crawler->childs[index] == NULL)
		{
			return false;
		}

		crawler = crawler->childs[index];
	}

	return true;  
}

void trieFree(Trie* obj) 
{
	free(obj);   
}

coding problems solutions