首页 > 代码库 > 208. Implement Trie (Prefix Tree)
208. Implement Trie (Prefix Tree)
Implement a trie with insert
, search
, and startsWith
methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z
.
class TrieNode { public TrieNode[] Child {get;set;} public bool EndWord {get;set;} // Initialize your data structure here. public TrieNode() { Child = new TrieNode[26]; EndWord = false; }}public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } // Inserts a word into the trie. public void Insert(String word) { var sentinel = root; for(int i =0;i<word.Length;i++) { if(sentinel.Child[word[i]-‘a‘] == null) sentinel.Child[word[i]-‘a‘] = new TrieNode(); sentinel = sentinel.Child[word[i]-‘a‘]; } sentinel.EndWord = true; } // Returns if the word is in the trie. public bool Search(string word) { var sentinel = root; for(int i =0;i<word.Length;i++) { if(sentinel.Child[word[i]-‘a‘] == null) return false; sentinel = sentinel.Child[word[i]-‘a‘]; } return sentinel.EndWord; } // Returns if there is any word in the trie // that starts with the given prefix. public bool StartsWith(string word) { var sentinel = root; for(int i =0;i<word.Length;i++) { if(sentinel.Child[word[i]-‘a‘] == null) return false; sentinel = sentinel.Child[word[i]-‘a‘]; } return true; }}// Your Trie object will be instantiated and called as such:// Trie trie = new Trie();// trie.Insert("somestring");// trie.Search("key");
208. Implement Trie (Prefix Tree)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。