[leetcode trie]212. Word Search II

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"].

题意：查找哪些单词在二维字母数组中出现

思路：1.用所有的单词建立字典树

　　　2.遍历二维数组中的所有位置，以这个位置开头向二维数组上下左右方向扩展的字符串是否在字典树中出现

　　评论区还有一种用复数和字典树的解题方法，太帅了

 class Solution(object):

     def findWords(self, board, words):

         trie = {}

         for w in words:

             cur = trie

             for c in w:

                 cur = cur.setdefault(c,{})

             cur[None] = None

         self.flag = [[False]*len(board[0]) for _ in range(len(board))]

         self.res = set()

         for i in range(len(board)):

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

                 self.find(board,trie,i,j,'')

         return list(self.res)

     def find(self,board,trie,i,j,str):

         if None in trie:

             self.res.add(str)

         if i<0 or i>=len(board) or j<0 or j>=len(board[0]):

             return

         if not self.flag[i][j] and board[i][j] in trie:

             self.flag[i][j] = True

             self.find(board,trie[board[i][j]],i-1,j,str+board[i][j])

             self.find(board,trie[board[i][j]],i+1,j,str+board[i][j])

             self.find(board,trie[board[i][j]],i,j+1,str+board[i][j])

             self.find(board,trie[board[i][j]],i,j-1,str+board[i][j])

             self.flag[i][j] = False

         return

巴特西

[leetcode trie]212. Word Search II

最新文章

热门文章