LeetCode -- Implement Trie (Prefix Tree)

LeetCode -- Implement Trie (Prefix Tree)

題目描述：
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.




思路：
1.由於題目可以假設所有input均為小寫字母，因此每個節點存1個字符。
2.root的val保持空
3.創建樹時，不斷拿去當前word[i]的字符,i∈[0,n)，如果word[i]在當前node的children中找不到，就添加到children中。同時把最後一個節點標記（hasWord）為是否為單詞的末尾。
4.搜索時，每次拿word[i]的字符，逐層判斷即可。如果是Search，判斷最後到達的字符是否標記為hasWord；如果僅僅搜索prefix，只需判斷i是否到word結尾即可。






實現代碼：

public class TrieNode {
    // Initialize your data structure here.
    public TrieNode() {
		children = new List();
		hasWord = false;
    }
	public TrieNode(char v){
		val = v;
		children = new List();
		hasWord = false;
	}
	
	public IList children;
	public char val;
	public bool hasWord ;
}


public class Trie {
    public TrieNode root;


    public Trie() {
        root = new TrieNode();
    }


    // Inserts a word into the trie.
    public void Insert(String word) {
		if(string.IsNullOrEmpty(word)){
			return;
		}
		var n = root;
		var index = 0;
		
		// try find
		while(n.children.Count > 0 && index < word.Length){
			var first = n.children.FirstOrDefault(x=>x.val == word[index]);
			if(first != null){
				n = first;
				index++;
			}
			else{
				break;
			}
		}
		if(index < word.Length){
			// if not exist , create new node
			for(var i = index; i < word.Length; i++){
				var child = new TrieNode(word[i]);
				n.children.Add(child);
				n = child;
			}
		}
		n.hasWord = true;
		
    }


    // Returns if the word is in the trie.
    public bool Search(string word) {
		TrieNode n = null;
		var index = TryFindNode(word, out n);
		return index == word.Length && n.hasWord;
    }
	
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public bool StartsWith(string word) {
		TrieNode n = null;
		var index = TryFindNode(word, out n);
		return index == word.Length;
    }
	
	private int TryFindNode(string word, out TrieNode node){
		var n = root;
		
		var index = 0;
		while(n.children.Count > 0 && index < word.Length){
			var first = n.children.FirstOrDefault(x => x.val == word[index]);
			if(first != null){
				n = first;
				index++;
			}
			else{
				break;
			}
		}
		
		node = n;;
		return index;
	}


}