題目連結(jié)：
題目意譯：
在英文中，我們有一種概念稱為「字根」，其可以在後面接著其他字詞來形成另一個更長的字詞——稱此種字詞為派生詞（Derivative）。例如說，當(dāng)字根 "help" 緊接著字詞 "ful" 時，我們可以形成一個派生詞 "helpful"。
給定一個由若干個字根組成的字典 dictionary，以及一個由若干個字詞並且之間由空白隔開所組成的句子 sentence，將句子所有派生詞替換成其字根。如果一個派生詞可以被替換成多個字根，則取最短者來替換。
回傳經(jīng)過替換後的句子。
限制：
1 ≦ dictionary.length ≦ 1000
1 ≦ dictionary[i].length ≦ 100
dictionary[i] 只由小寫英文字母組成。
1 ≦ sentence.length ≦ 10 ^ 6
sentence 只由小寫字母以及空白組成。
sentence 中的字詞數(shù)位於範(fàn)圍 [1, 1000] 中。
sentence 中每一個字詞之長度位於範(fàn)圍 [1, 1000] 中。
每兩個連續(xù)字詞之間只會由恰好一個空白隔開。
sentence 沒有前導(dǎo)和末尾空白。
範(fàn)例測資：
範(fàn)例 1：
輸入： dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
輸出： "the cat was rat by the bat"
範(fàn)例 2：
輸入： dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
輸出： "a a b c"
解題思維：
先用 dictionary 建立出一棵對應(yīng)的前綴樹（Trie，可以參見維基）。
然後對於 sentence 中每一個字詞在前綴樹中找最短的字根來替換即可（如果存在對應(yīng)字根的話）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
