首页 > 代码库 > 208. Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree)

Implement a trie with insertsearch, 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)