【題目描述】
Given a matrix of lower alphabetsand a dictionary.Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position.
給出一個由小寫字母組成的矩陣和一個字典。找出所有同時在字典和矩陣中出現(xiàn)的單詞。一個單詞可以從矩陣中的任意位置開始，可以向左/右/上/下四個相鄰方向移動。
【題目鏈接】
www.lintcode.com/en/problem/word-search-ii/
【題目解析】
將待查找的單詞儲存在字典樹Trie中，使用DFS（深度優(yōu)先搜索）在格板中查找，利用字典樹剪枝。
每當(dāng)找到一個單詞時，將該單詞從字典樹中刪去。返回結(jié)果按照字典序遞增排列。
哈希表在此題中不適用，因為單詞前綴的存儲會消耗大量的空間。
【參考答案】
