【题目描述】
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.
给出一个由小写字母组成的矩阵和一个字典。找出所有同时在字典和矩阵中出现的单词。一个单词可以从矩阵中的任意位置开始，可以向左/右/上/下四个相邻方向移动。
【题目链接】
www.lintcode.com/en/problem/word-search-ii/
【题目解析】
将待查找的单词储存在字典树Trie中，使用DFS（深度优先搜索）在格板中查找，利用字典树剪枝。
每当找到一个单词时，将该单词从字典树中删去。返回结果按照字典序递增排列。
哈希表在此题中不适用，因为单词前缀的存储会消耗大量的空间。
【参考答案】
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/31475320/viewspace-2142107/ ，如需转载，请注明出处，否则将追究法律责任。
请登录后发表评论
登录
全部评论
