Leetcode題解 Python & C#：五月挑戰DAY14 Implement Trie (Prefix Tree)

要實作 trie ，有 insert, search 和 startsWith 的功能。

trie 很實用，但在 algorithm 中，不太好用上這樣的方法解題。昨日在學 cisco ，就使用 trie 來加速指今輸入。

由於 Leetcode 有教學，這裡就不多說如何解題。(如果懂 trie 是怎樣的型態就會知道要怎麼寫)

Python

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        now = self.trie
        for char in word:
            if char not in now: now[char] = {}                
            now = now[char]
        now['exist'] = True
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        now = self.trie
        for char in word:
            if char not in now: return False
            now = now[char]
        return 'exist' in now 
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        now = self.trie
        for char in prefix:
            if char not in now: return False
            now = now[char]
        return True 

C#

class TrieNode
{
    public bool End;
    public Dictionary Next;
    public TrieNode() {   
        Next = new Dictionary();
        End = false;
    }
}

public class Trie {
    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void Insert(string word) {
        TrieNode now = root;
        foreach(char c in word)
        {
            if(!(now.Next.ContainsKey(c)))
            {
                now.Next[c] = new TrieNode();
            }
            now = now.Next[c];
        }
        now.End = true;
    }
    
    /** Returns if the word is in the trie. */
    public bool Search(string word) {
        TrieNode now = root;
        foreach(char c in word)
        {            
            if(now.Next.ContainsKey(c))
            {
                now = now.Next[c];
            }
            else
            {
                return false;
            }
        }
        return now.End;        
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public bool StartsWith(string prefix) {
        TrieNode now = root;
        foreach(char c in prefix)
        {            
            if(now.Next.ContainsKey(c))
            {
                now = now.Next[c];
            }
            else
            {
                return false;
            }
        }
        return true;
    }
}