183 - 212 单词搜索2

题目

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入: words = ["oath","pea","eat","rain"] and board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ]

输出: ["eat","oath"]

说明:

• 你可以假设所有输入都由小写字母 a-z 组成。

提示:

• 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？

• 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

解答

根据提示，应该把words里面单词插入前缀树里面，回溯的时候调用startwith，如果没有了就弹出

字典树

https://leetcode-cn.com/problems/word-search-ii/solution/qian-zhui-shu-dfs-by-powcai/

这个就没用前缀树，就比较好理解吧😂

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        trie = {}
        for word in words:
            t = trie
            for w in word:
                t = t.setdefault(w, {})
            t["end"] = 1
        print(trie)
        res = []
        row = len(board)
        col = len(board[0])
        direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]

        def dfs(i, j, trie, s):
            c = board[i][j]
            if c not in trie:
                return
            trie = trie[c]
            if "end" in trie and trie["end"] == 1:
                res.append(s+c)
                trie["end"] = 0
            board[i][j] = "#"
            for x, y in direction:
                tmp_i = x+i
                tmp_j = y+j
                if 0 <= tmp_i and tmp_i < row and 0 <= tmp_j \
                        and tmp_j < col and board[tmp_i][tmp_j] != "#":
                    dfs(tmp_i, tmp_j, trie, s+c)
            board[i][j] = c

        for i in range(row):
            for j in range(col):
                dfs(i, j, trie, "")
        return res

Runtime: 280 ms, faster than 82.03% of Python3 online submissions for Word Search II.

Memory Usage: 28.7 MB, less than 91.67% of Python3 online submissions for Word Search II.

前缀树

https://leetcode.com/problems/word-search-ii/discuss/59790/Python-dfs-solution-(directly-use-Trie-implemented).

class TrieNode():
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.isWord = False

class Trie():
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for w in word:
            node = node.children[w]
        node.isWord = True

    def search(self, word):
        node = self.root
        for w in word:
            node = node.children.get(w)
            if not node:
                return False
        return node.isWord

class Solution(object):
    def findWords(self, board, words):
        res = []
        trie = Trie()
        node = trie.root
        for w in words:
            trie.insert(w)
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.dfs(board, node, i, j, "", res)
        return res

    def dfs(self, board, node, i, j, path, res):
        if node.isWord:
            res.append(path)
            node.isWord = False
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
            return 
        tmp = board[i][j]
        node = node.children.get(tmp)
        if not node:
            return 
        board[i][j] = "#"
        self.dfs(board, node, i+1, j, path+tmp, res)
        self.dfs(board, node, i-1, j, path+tmp, res)
        self.dfs(board, node, i, j-1, path+tmp, res)
        self.dfs(board, node, i, j+1, path+tmp, res)
        board[i][j] = tmp

Runtime: 440 ms, faster than 30.82% of Python3 online submissions for Word Search II.

Memory Usage: 36 MB, less than 66.67% of Python3 online submissions for Word Search II.