Word Search II

男娘i 2021-12-17 10:39 187阅读 0赞

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`.

这题是[Word Search][]的follow up, 与word search I只查找一个单词不一样，这里需要查找多个单词是否存在．如果使用Ｉ的方法，每个单词都要扫描一遍board,显然效率比较低．我们可以利用子典里单词的公共特性．就是公共前缀等．建立一个prefix-tree, trie.如果当前路径不是哪个单词的前缀就可以停止．避免了反复扫描．

代码如下：

class TrieNode(object):
        def __init__(self):
            self.children = {}
            self.word = None
            
    class Trie(object):
        def __init__(self):
            self.root = TrieNode()
    
        def insert(self, word):
            node = self.root
            for i in word:
                if not node.children.get(i):
                    node.children[i] = TrieNode()
                node = node.children[i]
            node.word = word
    
    class Solution(object):
        def findWords(self, board, words):
            if not board:
                return []
            trie = Trie()
            for word in words:
                trie.insert(word)
            res = []
            for i in xrange(len(board)):
                for j in xrange(len(board[0])):
                    self.dfs(board, i, j, res, trie.root)
            return res
            
        def dfs(self, board, i, j, res, root):
            c = board[i][j]
            if c == '#' or not root.children.get(c):
                return 
            p = root.children[c]
            if p.word:
                res.append(p.word)
                p.word = None
            board[i][j] = '#'
            if i > 0: self.dfs(board, i-1, j, res, p)
            if j > 0: self.dfs(board, i, j-1, res, p)
            if i < len(board)-1: self.dfs(board, i+1, j, res, p)
            if j < len(board[0])-1: self.dfs(board, i, j + 1, res, p)
            board[i][j] = c

转载于:https://www.cnblogs.com/sherylwang/p/5643710.html

[Word Search]: http://www.cnblogs.com/sherylwang/p/5641718.html