主題
題目連結(jié)：
題目意譯：
給定一個(gè)字串陣列 products 以及一個(gè)字串 searchWord 。我們想要設(shè)計(jì)一個(gè)系統(tǒng)其可以在 searchWord 每個(gè)字元每輸入時(shí)顯示最多三個(gè) products 中的建議產(chǎn)品名稱。建議產(chǎn)品應(yīng)與 searchWord 有共同的前綴。如果有多於三個(gè)產(chǎn)品其與 searchWord 有著共同前綴，則回傳前三個(gè)字典序最小的。
回傳一個(gè)列表的列表，每個(gè)子列表包含著每輸入一個(gè) searchWord 的字母時(shí)會(huì)有的建議產(chǎn)品名稱。
限制：
1 ≦ products.length ≦ 1000
products 中沒(méi)有重複的元素。
1 ≦ Σ products[i].length ≦ 2 × 10 ^ 4
所有 procucuts[i] 之字元皆為小寫英文字母。
1 ≦ searchWord.length ≦ 1000
所有 searchWord 之字元皆為小寫英文字母。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
輸出： [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解釋： products 按照字典序排序 = ["mobile","moneypot","monitor","mouse","mousepad"]
輸入 m 和 mo 後，所有產(chǎn)品皆符合而我們顯示給使用者的為 ["mobile","moneypot","monitor"]
輸入 mou 、 mous 和 mouse 後，系統(tǒng)將建議 ["mouse","mousepad"]
範(fàn)例 2：
輸入： products = ["havana"], searchWord = "havana"
輸出： [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
範(fàn)例 3：
輸入： products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
輸出： [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
範(fàn)例 4：
輸入： products = ["havana"], searchWord = "tatiana"
輸出： [[],[],[],[],[],[],[]]
解題思維：
先將所有產(chǎn)品名稱之字串陣列 products 按照字典序由小到大排序。這樣我們等等就不需煩惱字典序的問(wèn)題。
然後我們利用一個(gè)布林陣列 P，其中 P[i] 代表 products[i] 於先前與 searchWord 之比對(duì)有無(wú)符合。而一開(kāi)始我們還沒(méi)做任何比對(duì)，所以所有的 P[i] 之值都設(shè)為真（代表所有產(chǎn)品都符合目前的搜尋）。
接著我們就開(kāi)始掃過(guò) searchWord 的每個(gè)字元。對(duì)於每個(gè)字元 searchWord[i] 去遍歷一次所有的 products[j]。對(duì)於每個(gè) products[j]，我們先判斷 products[j] 於前一次比對(duì)是否仍符合，即 P[j] 之值。如果 P[j] 已為假就代表該產(chǎn)品再繼續(xù)比較也沒(méi)有意義（也不會(huì)被納入選擇之中），因此可以繼續(xù)到下一個(gè)字串。
如果前一次有符合，則我們?cè)贆z查 searchWord[i] 是否與 products[j] 的第 i 個(gè)字元（即 products[j][i]）相同。如果相同，則對(duì)於此次搜尋，products[j] 將是建議產(chǎn)品名稱之一；反之，則對(duì)於本次以及其後所有比對(duì)，products[j] 都不會(huì)再是建議產(chǎn)品名稱之一，因此此時(shí)我們將 P[j] 之值設(shè)為假。
然後將每個(gè) searchWord[i] 所得的搜尋建議前三個(gè)（如果夠三個(gè)的話）包成一個(gè)列表，然後這些列表再用另一個(gè)列表包起來(lái)即是所求。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
