题目描述

给出一个由小写字母组成的矩阵和一个字典。找出所有同时在字典和矩阵中出现的单词。一个单词可以从矩阵中的任意位置开始，可以向左/右/上/下四个相邻方向移动。一个字母在一个单词中只能被使用一次。且字典中不存在重复单词。

---

测试样例

输入：["doaf","agai","dcan"]，["dog","dad","dgdg","can","again"]

输出：["again","can","dad","dog"]

解释：

  d o a f

  a g a i

  d c a n

矩阵中查找，返回 ["again","can","dad","dog"]。

输入：["a"]，["b"]

输出：[]

解释：

a

矩阵中查找，返回 []。

---

解题思路

刚开始读完题目和看完测试样例时一脸懵逼..其实题目意思是，从矩阵中任何一个位置出发，可以上、下、左、右移动，判断移动过程中组成的单词是否在字典中。另外，题目描述中“一个字母在一个单词中只能被使用一次”的实际意思是，矩阵中一个位置的字母在同一个单词中只能被使用一次，这里容易误解为一个单词中不存在重复的字母。

1、DFS

i). 先进行预处理，记录字典中所有单词的前缀（包括单词本身）集合 prefix_set，这个集合可用于判断搜索路径的有效性；

ii). 从矩阵的每个位置出发进行递归搜索，标记该位置为已使用，待搜索完毕后再取消标记；

iii). 在递归搜索过程中，先判断当前路径组成的单词是否在前缀集合中，若不在，则结束搜索；

iv). 在递归搜索过程中，判断当前路径组成的单词是否在字典中，若是，则代表已经搜索到一个单词，将其加入结果，但是并不终止搜索，这点需要注意！

v). 分别向上、下、左、右四个方向移动，注意先判断移动后的位置是否在矩阵范围内，以及该位置是否已被使用；

vi). 移动后得到矩阵对应位置的字母，继续递归搜索，同时标记该位置为已使用，待搜索完再取消标记

2、Trie

Trie是一种树形结构，是哈希树的变种。典型应用是统计、排序和保存大量的字符串（但不仅限于字符串），因此经常被搜索引擎系统用于文本词频统计。

i). 构建Trie节点数据结构TrieNode，有两个成员属性：children: dict 和 word: str，children的key是字典中单词的字母，value是TrieNode对象；word仅当在叶子节点中才会被设置（初始化为None），设置为字典中的单词，叶子节点的children的key对应该词的最后一个字母；

ii). 构建Trie数据结构，有一个成员属性root: TrieNode，以及一个insert()方法，参数是字典中的单词，这样就可以将单词的每个字母设置到各个children的key，充当了方法1中prefix_set的作用；

iii). 从矩阵中的每个位置出发进行递归搜索，标记该位置为已使用，待搜索结束后取消。在搜索过程中，若当前节点的word成员属性被设置并且未被加入到结果中，则加入到结果列表result中；

iv). 分别向上、下、左、右移动，和方法1类似，先判断移动后位置的有效性、是否被使用，这里还需要判断移动后对应位置的字母是否在当前节点的children中，如果不在，说明沿这个方向搜索下去得到的单词不会在字典中；

v). 若移动后获得一个有效位置，则标记该位置为已使用并进一步递归搜索，待搜索完毕后取消标记

---

代码

1、DFS

class Solution:

    """

    @param board: A list of lists of character

    @param words: A list of string

    @return: A list of string

    """

    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

    def wordSearchII(self, board, words):

        if not board or not words:

            return []

        # 记录当前位置的字符是否被使用

        used = {}

        result = set()

        # 字典中每个单词的前缀集合

        # 通过这个集合可判断每条搜索路径是否可能成功

        prefix_set = set()

        for word in words:

            for i in range(1, len(word) + 1):

                prefix = word[:i]

                prefix_set.add(prefix)

        for row in range(len(board)):

            for col in range(len(board[0])):

                pos = (row, col)

                used[pos] = True

                self._search(pos, board[row][col], board, words, prefix_set, used, result)

                del used[pos]

        # 最后需转换成list，不然会报错

        return list(result)

    def _search(self, pos, word, board, words, prefix_set, used, result):

        # 若当前搜索到的字符组合不在前缀集合中，

        # 则终止搜索

        if word not in prefix_set:

            return

        # 若当前搜索到的字符组合在字典中，

        # 则说明已形成字典中的单词，加入结果

        # 注意，这里并不终止搜索！

        if word in words:

            result.add(word)

        row, col = pos

        for delta_y, delta_x in self.directions:

            row_new = row + delta_y

            col_new = col + delta_x

            pos_new = (row_new, col_new)

            # 判断移动到的位置是否在矩阵范围内

            if not self._is_valid(pos_new, board):

                continue

            # 判断移动到的位置对应的字符是否已使用

            # （一个字母在同一单词中仅允许出现一次）

            if pos_new in used:

                continue

            used[pos_new] = True

            self._search(pos_new, word + board[row_new][col_new], board, words, prefix_set, used, result)

            del used[pos_new]

    def _is_valid(self, pos, board):

        row, col = pos

        return 0 <= row < len(board) and 0 <= col < len(board[0])

2、Trie

class TrieNode:

    def __init__(self):

        self.children = {}

        self.word = None

class Trie:

    def __init__(self):

        self.root = TrieNode()

    def insert(self, word):

        node = self.root

        for c in word:

            if c not in node.children:

                node.children[c] = TrieNode()

            node = node.children[c]

        node.word = word

class Solution:

    """

    @param board: A list of lists of character

    @param words: A list of string

    @return: A list of string

    """

    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

    def wordSearchII(self, board, words):

        if not board or not words:

            return []

        result = []

        trie = Trie()

        # 构建单词树，在叶子节点中设置对应的word

        for word in words:

            trie.insert(word)

        root = trie.root

        for row in range(len(board)):

            for col in range(len(board[0])):

                if board[row][col] in root.children:

                    pos = (row, col)

                    self._search(board, root.children[board[row][col]], pos, {pos: True}, result)

        return result

    def _search(self, board, node, pos, used, result):

        if node.word and node.word not in result:

            result.append(node.word)

        row, col = pos

        for delta_y, delta_x in self.directions:

            row_new = row + delta_y

            col_new = col + delta_x

            pos_new = (row_new, col_new)

            # 判断移动到的位置是否在矩阵范围内

            if not self._is_valid(pos_new, board):

                continue

            # 判断移动到的位置对应的字符是否已使用

            # （一个字母在同一单词中仅允许出现一次）

            if pos_new in used:

                continue

            # 下一个字母必须在当前节点的孩子中

            if board[row_new][col_new] not in node.children:

                continue

            used[pos_new] = True

            self._search(board, node.children[board[row_new][col_new]], pos_new, used, result)

            del used[pos_new]

    def _is_valid(self, pos, board):

        row, col = pos

        return 0 <= row < len(board) and 0 <= col < len(board[0])