212. Word Search II
給定一個 m x n 的字符板和一個字符串列表 words，返回板上所有可以找到的單詞。
每個單詞必須由順序相鄰的單元格中的字母組成，其中相鄰單元格是水平或垂直相鄰的。同一單元格中的字母在一個單詞中不能被多次使用。
範例：
輸入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
輸出：["eat","oath"]
Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
self.word = None
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
node.word = word
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# Build the Trie
trie = Trie()
for word in words:
trie.insert(word)
result = []
rows, cols = len(board), len(board[0])
def dfs(node, x, y):
char = board[x][y]
child_node = node.children.get(char)
if child_node is None:
return
if child_node.is_end_of_word:
result.append(child_node.word)
child_node.is_end_of_word = False # Avoid duplicate entries
board[x][y] = '#' # Mark the cell as visited
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and board[nx][ny] != '#':
dfs(child_node, nx, ny)
board[x][y] = char # Unmark the cell
for i in range(rows):
for j in range(cols):
dfs(trie.root, i, j)
return result
18.20MB, 4852ms
C++
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool is_end_of_word;
string word;
TrieNode() : is_end_of_word(false), word("") {}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->is_end_of_word = true;
node->word = word;
}
};
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
Trie trie;
for (string word : words) {
trie.insert(word);
}
vector<string> result;
int rows = board.size();
int cols = board[0].size();
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
dfs(board, trie.root, i, j, result);
}
}
return result;
}
private:
void dfs(vector<vector<char>>& board, TrieNode* node, int x, int y, vector<string>& result) {
char c = board[x][y];
if (c == '#' || node->children.find(c) == node->children.end()) {
return;
}
node = node->children[c];
if (node->is_end_of_word) {
result.push_back(node->word);
node->is_end_of_word = false; // Avoid duplicate entries
}
board[x][y] = '#'; // Mark the cell as visited
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()) {
dfs(board, node, nx, ny, result);
}
}
board[x][y] = c; // Unmark the cell
}
};
18.62MB, 796ms
Javascript
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
this.word = null;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
node.word = word;
}
}
/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
var findWords = function(board, words) {
const trie = new Trie();
for (const word of words) {
trie.insert(word);
}
const result = [];
const rows = board.length;
const cols = board[0].length;
const dfs = (node, x, y) => {
const char = board[x][y];
const childNode = node.children[char];
if (!childNode) return;
if (childNode.isEndOfWord) {
result.push(childNode.word);
childNode.isEndOfWord = false; // Avoid duplicate entries
}
board[x][y] = '#'; // Mark the cell as visited
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && board[nx][ny] !== '#') {
dfs(childNode, nx, ny);
}
}
board[x][y] = char; // Unmark the cell
};
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
dfs(trie.root, i, j);
}
}
return result;
};
57.78MB, 777ms
