Leetcode 212:单词搜索 II(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 212:单词搜索 II(超详细的解法!!!)

in leetcode with 0 comment

给定一个二维网格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组成。

提示:

解题思路

这个问题是之前问题Leetcode 79:单词搜索(最详细的解法!!!)提升,显然可以在之前代码的基础上做一些修改实现它。

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board:
            return []
        
        direct = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        r, c = len(board), len(board[0])
        board_c = collections.Counter([c for row in board for c in row])
        
        def _exist(i, j, k, word, visited):
            if k + 1 == len(word):
                return word[k] == board[i][j]

            if board[i][j] == word[k]:
                visited[i][j] = True
                for x, y in direct:
                    nx, ny = x + i, y + j
                    if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]\
                        and _exist(nx, ny, k + 1, word, visited):
                        return True
                visited[i][j] = False
            return False
   
        def exist(word):
            word_c = collections.Counter(word)
            for ch in word_c:
                if not ch in word_c or word_c[ch] > board_c[ch]:
                    return False

            for i in range(r):
                for j in range(c):  
                    if board[i][j] == word[0]:
                        visited = [[False]*c for _ in range(r)]
                        if _exist(i, j, 0, word, visited):
                            return True
            return False
        return [word for word in words if exist(word)]

但是上面这种做法超时了,那怎么办?单词查找问题应该使用Trie这个数据结构,Leetcode 208:实现 Trie (前缀树)

class Node:
    def __init__(self, isWord=False):
        self.isWord = isWord
        self.next = collections.defaultdict(Node)
        
class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word):
        cur = self.root
        for c in word:
            cur = cur.next[c]
            
        if not cur.isWord:
            cur.isWord = True
        
    def search(self, word):
        cur = self._search(word)
        return cur != None and cur.isWord
        
    def _search(self, word):
        cur = self.root
        for c in word:
            cur = cur.next.get(c)
            if not cur:
                return None
        return cur
        
    def startsWith(self, prefix):
        return self._search(prefix) != None 

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board:
            return []
        
        direct = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        r, c, trie, res = len(board), len(board[0]), Trie(), []
        visited = [[False]*c for _ in range(r)]
        for word in words:
            trie.insert(word)
        
        def dfs(i, j, path, visited, node):
            if node.isWord:
                res.append(path)
                node.isWord = False
                
            if i < 0 or i >= r or j < 0 or j >= c or visited[i][j]:
                return
            
            node = node.next.get(board[i][j])
            if not node:
                return 
            
            visited[i][j] = True
            for x, y in direct:
                nx, ny = x + i, y + j
                dfs(nx, ny, path+board[i][j], visited, node)
            visited[i][j] = False
   
        for i in range(r):
            for j in range(c):  
                dfs(i, j, "", visited, trie.root)
        return res

更加简洁的写法

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        direct = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        r, c, res = len(board), len(board[0]), []
        
        root = {}
        for word in words:
            node = root
            for i in word:
                if i not in node:
                    node[i] = {}
                node = node[i]
            node['#'] = word # 1
        
        def dfs(i, j, node):
            if i < 0 or i >= r or j < 0 or j >= c\
                or board[i][j] not in node:
                return
            
            tmp, board[i][j] = board[i][j], '$'
            node = node[tmp]
            if '#' in trie:
                res.append(node.pop('#'))
            
            for x, y in direct:
                nx, ny = x + i, y + j
                dfs(nx, ny, node)
            board[i][j] = tmp
            if not trie: # 2 
                node.pop(tmp)
   
        for i in range(r):
            for j in range(c):  
                dfs(i, j, root)
        return res

上面代码中有两个值得注意的细节,1:通过在单词结尾添加符号'#'来确定结尾位置,同时将单词存入其中,这种我们就不用遍历的过程中,一个字符一个字符的构建单词。2:当trie==None的时候表示没有以tmp结尾的单词,那么将其弹出,进行剪枝操作。

但是细节1对于其他语言不一定适用(容器中不能包含不同类型),所以我们可以这样写:

class Node:
    def __init__(self, wordId=-1):
        self.wordId = wordId
        self.next = collections.defaultdict(Node)
        
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        direct = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        r, c, res = len(board), len(board[0]), []
        
        root = Node()
        for i, word in enumerate(words):
            node = root
            for k in word:
                node = node.next[k]
            node.wordId = i
        
        def dfs(i, j, node):
            if i < 0 or i >= r or j < 0 or j >= c\
                or board[i][j] not in node.next:
                return
            
            tmp, board[i][j] = board[i][j], '$'
            node = node.next[tmp]
            if node.wordId != -1:
                res.append(words[node.wordId])
                node.wordId = -1
            
            for x, y in direct:
                nx, ny = x + i, y + j
                dfs(nx, ny, node)
            board[i][j] = tmp
   
        for i in range(r):
            for j in range(c):  
                dfs(i, j, root)
        return res

但是这么做了之后我们又无法使用优化2了,所以代码的效率需要根据实际应用场景进行考量。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses