題目208：前綴樹?是一種樹形數(shù)據(jù)結(jié)構(gòu)劲妙，用于高效地存儲和檢索字符串?dāng)?shù)據(jù)集中的鍵贬丛。
請你實現(xiàn) Trie 類：Trie()?初始化前綴樹對象迎献。void insert(String word)?向前綴樹中插入字符串?word?勋眯。boolean search(String word)?如果字符串?word?在前綴樹中，返回?true（即矗积，在檢索之前已經(jīng)插入）；否則敞咧，返回?false?棘捣。boolean startsWith(String prefix)?如果之前已經(jīng)插入的字符串word?的前綴之一為?prefix?，返回?true?休建；否則乍恐，返回?false?。
思路：樹狀結(jié)構(gòu)丰包，可以直接指向子節(jié)點（子節(jié)點的值為字母）禁熏。我們這里用的是指向一個字典。字典的鍵是字母邑彪，鍵值是下一級節(jié)點瞧毙。
題目211：請你設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，支持 添加新單詞 和 查找字符串是否與任何先前添加的字符串匹配 寄症。
實現(xiàn)詞典類?WordDictionary?：WordDictionary()?初始化詞典對象宙彪；void addWord(word)?將?word?添加到數(shù)據(jù)結(jié)構(gòu)中，之后可以對它進行匹配有巧；bool search(word)?如果數(shù)據(jù)結(jié)構(gòu)中存在字符串與word?匹配释漆，則返回?true?；否則篮迎，返回?false?男图。word?中可能包含一些?'.'?，每個.?都可以表示任何一個字母甜橱。
題目212：給定一個m x n?二維字符網(wǎng)格board?和一個單詞列表?words逊笆，返回所有二維網(wǎng)格上的單詞。
思路：把單詞列表上的詞匯建立一個前綴樹岂傲。然后遍歷網(wǎng)格难裆，在這棵樹上搜索。
題目1268：產(chǎn)品數(shù)組product中每個產(chǎn)品都是一個字符串镊掖。請你設(shè)計一個推薦系統(tǒng)乃戈，在依次輸入單詞searchWord?的每一個字母后，推薦products?數(shù)組中前綴與searchWord?相同的最多三個產(chǎn)品亩进。如果前綴相同的可推薦產(chǎn)品超過三個症虑，請按字典序返回最小的三個。
思路：先用產(chǎn)品數(shù)組建立一個前綴樹归薛。TrieNode isend的屬性可以不用谍憔，加一個推薦產(chǎn)品的屬性驶冒。因此在建立前綴樹的時候，每個節(jié)點都要有自己的推薦產(chǎn)品韵卤，如果推薦產(chǎn)品超過三個，就排序后舍棄最后一個崇猫。
