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.
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('\0'); } 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); }
0 Comments