Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link
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.length
n == board[i].length
1 <= m, n <= 12
board[i][j]
is a lowercase English letter.1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i]
consists of lowercase English letters.- All the strings of
words
are unique.
內容目錄
TogglePython
# time complexity: O(M(4*3^(L-1)))
# space complexity: O(n)
from typing import List
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
WORDKEY = "$"
trie = {}
for word in words:
node = trie
for letter in word:
node = node.setdefault(letter, {})
node[WORDKEY] = word
rowNum = len(board)
colNum = len(board[0])
matchedWords = []
def backtracking(row, col, parent):
letter = board[row][col]
currNode = parent[letter]
wordMatch = currNode.pop(WORDKEY, False)
if wordMatch:
matchedWords.append(wordMatch)
board[row][col] = "#"
for rowOffset, colOffset in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
newRow, newCol = row + rowOffset, col + colOffset
if (
newRow < 0
or newRow >= rowNum
or newCol < 0
or newCol >= colNum
):
continue
if not board[newRow][newCol] in currNode:
continue
backtracking(newRow, newCol, currNode)
board[row][col] = letter
if not currNode:
parent.pop(letter)
for row in range(rowNum):
for col in range(colNum):
if board[row][col] in trie:
backtracking(row, col, trie)
return matchedWords
# time complexity: O(n*3^l)
# space complexity: O(m)
class TrieNode:
def __init__(self, char=""):
self.char = char
self.children = {}
self.isEnd = False
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.get(c)
node.isEnd = True
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
def removeChars(self, word):
node = self.root
childList = []
for c in word:
childList.append([node, c])
node = node.children[c]
for parent, childChar in reversed(childList):
target = parent.children[childChar]
if target.children:
return
del parent.children[childChar]
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
def dfs(trieForWords: Trie, node: TrieNode, grid: List[List[str]], row: int, col: int, result: List[str], word=""):
if node.isEnd:
result.append(word)
node.isEnd = False
trieForWords.removeChars(word)
if 0 <= row < ROW and 0 <= col < COL:
char = grid[row][col]
child = node.children.get(char)
if child is not None:
word += char
grid[row][col] = None
for dR, dC in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
dfs(trieForWords, child, grid,
row + dR, col + dC, result, word)
grid[row][col] = char
ROW = len(board)
COL = len(board[0])
trieForWords = Trie()
result = []
for word in words:
trieForWords.insert(word)
for r in range(ROW):
for c in range(COL):
dfs(trieForWords, trieForWords.root, board, r, c, result)
return result
board = [["o", "a", "a", "n"],
["e", "t", "a", "e"],
["i", "h", "k", "r"],
["i", "f", "l", "v"]]
words = ["oath", "pea", "eat", "rain"]
print(Solution().findWords(board, words))