Description
Given a matrix of lower alphabets and 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. One character only be used once in one word. No same word in dictionary
Example
Example 1:
Input：["doaf","agai","dcan"]，["dog","dad","dgdg","can","again"]
Output：["again","can","dad","dog"]
Explanation：
d o a f
a g a i
d c a n
search in Matrix，so return ["again","can","dad","dog"].
Example 2:
Input：["a"]，["b"]
Output：[]
Explanation：
a
search in Matrix，return [].
Challenge
Using trie to implement your algorithm.
思路：
这个题和其他隐式图搜索的不同之处在于，最开始的时候就要从board中找出一个起点，所以这里要在递归函数外面循环board,然后开始进行搜索，同时结束递归的条件比较复杂， 要将words中所有单词的所有可能前缀排列都存储到hashmap中去，当得到的substring不在hashmap中即可返回。
代码：
网友评论