Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example 1:
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"]
Example 2:
Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 12-
board[i][j]is a lowercase English letter. 1 <= words.length <= 3 * 1041 <= words[i].length <= 10-
words[i]consists of lowercase English letters. - All the strings of
wordsare unique.
Ideas: 利用trie，首先利用[LeetCode] 208. Implement Trie (Prefix Tree)_Medium tag: Trie里面的trie的structure，将words里面的word都insert进入到trie里面。然后利用dfs，去判断该点是否在trie里面，如果在的话就继续dfs，否则不dfs，并且利用backtracking。另外有两个点需要注意，第一，因为要避免[[‘a‘, ‘b‘, ‘a‘]], words: [‘a‘], 最后结果为[‘a‘, ‘a‘]的情况，那么需要在dfs中每次append path进入到ans之后设置node.isWord = False， 就不会有重复的path情况。第二，在dfs时， 先判断node.isWord 是否为true， 不需要看i, j 为相应的range里面， 否则会miss掉一些情况。
T: O(len(words) * len(word) + (m * n) ^ 2), S: O(len(words) * len(word)）
Code
class TrieNode: def __init__(self): self.isWord = False self.children = dict() class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for c in word: if c not in node.children: node.children[c] = TrieNode() node = node.children[c] node.isWord = True class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: ans, trie, m, n = [], Trie(), len(board), len(board[0]) for word in words: trie.insert(word) for i in range(m): for j in range(n): self.dfs(board, i, j, "", trie.root, ans) return ans def dfs(self, board, i, j, path, node, ans): if node.isWord: ans.append(path) node.isWord = False if 0 <= i < len(board) and 0 <= j < len(board[0]): temp = board[i][j] if temp not in node.children: return node = node.children[temp] board[i][j] = ‘#‘ self.dfs(board, i + 1, j, path + temp, node, ans) self.dfs(board, i - 1, j, path + temp, node, ans) self.dfs(board, i, j + 1, path + temp, node, ans) self.dfs(board, i, j - 1, path + temp, node, ans) board[i][j] = temp