An Interest In:
Web News this Week
- March 18, 2024
- March 17, 2024
- March 16, 2024
- March 15, 2024
- March 14, 2024
- March 13, 2024
- March 12, 2024
Some of Our Sources
- Slashdot
- Engadget
- Web Designer Wall
- The Logo Smith
- Spoon Graphics
- Smashing Apps
- TutsPlus - Design
- CSS Tricks
- Freelance Switch
- The Verge
Help Webnuz
Referal links:
August 28, 2022 07:47 am GMT
Original Link: https://dev.to/salahelhossiny/implement-trie-16k2
Implement Trie
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 there is a previously inserted string word that has the prefix prefix, and false otherwise.
class TrieNode(): def __init__(self): self.children = {} self.endOfWord = Falseclass Trie: def __init__(self): self.root = TrieNode() def insert(word): cur = self.root for c in word: if c not in cur.children: cur.children[c] = TrieNode() cur = cur.children[c] cur.endOfWord = True def search(word): cur = self.root for c in word: if c not in cur.children: return False cur = cur.children[c] return cur.endOfWord def startsWith(prefix): cur = self.root for c in prefix: if c not in cur.children: return False cur = cur.children[c] return TrueOriginal Link: https://dev.to/salahelhossiny/implement-trie-16k2
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To