题目描述：
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board =
[ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] Return ["eat","oath"].
Note:
You may assume that all inputs are consist of lowercase letters a-z.
You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?
Hint:
If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.
题目大意：
给定二维格板和一组单词，在格板中找出这些单词。
每一个单词必须通过顺序邻接的单元格中的字母构成，“邻接”是指水平或者竖直方向相邻。同一个单元格中的字母在构建某个单词时最多只能使用一次。
测试用例见题目描述。
注意：
你可以假设输入只包含小写字母a-z
你需要最优化你的回溯策略，以通过数据规模比较大的测试样例。能不能尽可能早的停止回溯？
提示：
如果当前的候选单词在所有的单词前缀中都不存在，就可以立即停止回溯。什么样的数据结构可以更加有效地响应这种查询？哈希表可以吗？为什么可以或者不行？字典树怎么样？如果要了解字典树的基础知识，可以先完成这道题目：Implement Trie (Prefix Tree) ，实现字典树（前缀树）
解题思路：
将待查找的单词储存在字典树Trie中，使用DFS（深度优先搜索）在格板中查找，利用字典树剪枝。
每当找到一个单词时，将该单词从字典树中删去。
返回结果按照字典序递增排列。
哈希表在此题中不适用，因为单词前缀的存储会消耗大量的空间。
Python代码：
class Solution:
# @param {character[][]} board
# @param {string[]} words
# @return {string[]}
def findWords(self, board, words):
w, h = len(board[0]), len(board)
trie = Trie()
for word in words:
trie.insert(word)
visited = [[False] * w for x in range(h)]
dz = zip([1, 0, -1, 0], [0, 1, 0, -1])
ans = []
def dfs(word, node, x, y):
node = node.childs.get(board[x][y])
if node is None:
return
visited[x][y] = True
for z in dz:
nx, ny = x + z[0], y + z[1]
if nx >= 0 and nx < h and ny >= 0 and ny < w and not visited[nx][ny]:
dfs(word + board[nx][ny], node, nx, ny)
if node.isWord:
ans.append(word)
trie.delete(word)
visited[x][y] = False
for x in range(h):
for y in range(w):
dfs(board[x][y], trie.root, x, y)
return sorted(ans)
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.childs = dict()
self.isWord = False
class Trie:
def __init__(self):
self.root = TrieNode()
# @param {string} word
# @return {void}
# Inserts a word into the trie.
def insert(self, word):
node = self.root
for letter in word:
child = node.childs.get(letter)
if child is None:
child = TrieNode()
node.childs[letter] = child
node = child
node.isWord = True
def delete(self, word):
node = self.root
queue = []
for letter in word:
queue.append((letter, node))
child = node.childs.get(letter)
if child is None:
return False
node = child
if not node.isWord:
return False
if len(node.childs):
node.isWord = False
else:
for letter, node in reversed(queue):
del node.childs[letter]
if len(node.childs) or node.isWord:
break
return True
本文链接：http://bookshadow.com/weblog/2015/05/19/leetcode-word-search-ii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
