[leetcode] 第三十五部分(212)

212-Word Search II

问题描述

给定一个二维的面板和字典的词语列表, 找到面板中的所有词语.

每个词语必须由顺序相连的单元构成, 其中, "相连的" 单元为那些 横向或者纵向 的连接. 相同的字母在一个词语中不能使用超过一次.

示例

Input:
board = [
[‘o’,’a’,’a’,’n’],
[‘e’,’t’,’a’,’e’],
[‘i’,’h’,’k’,’r’],
[‘i’,’f’,’l’,’v’]
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

注意:

  • 所有的输入均由小写字母a-z组成
  • words中的所有值都是唯一的

解题思路

很明显, 当单词长度非常大的时候, 用 暴力破解 是无法解决的. 因此, 在这里, 需要我们使用 字典树 进行求解. 参考之前的211-Add and Search Word – Data structure design, 实现字典树中的insert功能, 然后配合一个深度优先搜索即可.

代码

class TrieNode(object):

    def __init__(self):
        self.children = dict()
        self.is_word = False

class Trie(object):

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

    def insert(self, word):
        node = self.root
        for i in range(len(word)):
            if word[i] in node.children:
                node = node.children[word[i]]
            else:
                node.children[word[i]] = TrieNode()
                node = node.children[word[i]]
        node.is_word = True

    def delete(self, word):
        node = self.root
        stack = []
        for i in range(len(word)):
            stack.append([node, word[i]])
            node = node.children[word[i]]
            if node is not None:
                return False
        if not node.is_word:
            return False
        elif node.children:
            node.is_word = False
            return True
        else:
            while stack:
                node, word = stack.pop()
                del node.children[word]
                if len(node.children) or node.is_word:
                    break
        return True

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        res = set()
        if len(words) == 0 or len(board) == 0 or len(board[0]) == 0:
            return res
        tree = Trie()
        visited = [[False] * len(board[i]) for i in range(len(board))]
        for i in range(len(words)):
            tree.insert(words[i])

        def dfs(x, y, root, word):
            root = root.children.get(board[x][y])
            if not root:
                return
            visited[x][y] = True
            for dx, dy in zip((1,0,-1,0), (0,1,0,-1)):
                nx = x + dx
                ny = y + dy
                if nx < 0 or ny < 0 or nx > len(board) - 1 or ny > len(board[nx]) - 1 or visited[nx][ny]:
                    continue
                dfs(nx, ny, root, word + board[nx][ny])
            if root.is_word:
                res.add(word)
                tree.delete(word)
            visited[x][y] = False

        for i in range(len(board)):
            for j in range(len(board[i])):
                dfs(i, j, tree.root, board[i][j])

        return list(res)
打赏

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注