Word Search II 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.
Word Search II Solutions
✅Time:O(mnmax(∣words[i]∣))
✅Space: O(Σ∣strings[i]∣)
C++
struct TrieNode {
vector<TrieNode*> children;
const string* word = nullptr;
TrieNode() : children(26) {}
~TrieNode() {
for (TrieNode* child : children)
delete child;
}
};
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> ans;
for (const string& word : words)
insert(word);
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board[0].size(); ++j)
dfs(board, i, j, &root, ans);
return ans;
}
private:
TrieNode root;
void insert(const string& word) {
TrieNode* node = &root;
for (const char c : word) {
if (!node->children[c - 'a'])
node->children[c - 'a'] = new TrieNode;
node = node->children[c - 'a'];
}
node->word = &word;
}
void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node,
vector<string>& ans) {
if (i < 0 || i == board.size() || j < 0 || j == board[0].size())
return;
if (board[i][j] == '*')
return;
const char c = board[i][j];
TrieNode* child = node->children[c - 'a'];
if (!child)
return;
if (child->word) {
ans.push_back(*child->word);
child->word = nullptr;
}
board[i][j] = '*';
dfs(board, i + 1, j, child, ans);
dfs(board, i - 1, j, child, ans);
dfs(board, i, j + 1, child, ans);
dfs(board, i, j - 1, child, ans);
board[i][j] = c;
}
};
Java
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public String word;
}
class Solution {
public List<String> findWords(char[][] board, String[] words) {
for (final String word : words)
insert(word);
List<String> ans = new ArrayList<>();
for (int i = 0; i < board.length; ++i)
for (int j = 0; j < board[0].length; ++j)
dfs(board, i, j, root, ans);
return ans;
}
private TrieNode root = new TrieNode();
private void insert(final String word) {
TrieNode node = root;
for (final char c : word.toCharArray()) {
if (node.children[c - 'a'] == null)
node.children[c - 'a'] = new TrieNode();
node = node.children[c - 'a'];
}
node.word = word;
}
private void dfs(char[][] board, int i, int j, TrieNode node, List<String> ans) {
if (i < 0 || i == board.length || j < 0 || j == board[0].length)
return;
if (board[i][j] == '*')
return;
final char c = board[i][j];
TrieNode child = node.children[c - 'a'];
if (child == null)
return;
if (child.word != null) {
ans.add(child.word);
child.word = null;
}
board[i][j] = '*';
dfs(board, i + 1, j, child, ans);
dfs(board, i - 1, j, child, ans);
dfs(board, i, j + 1, child, ans);
dfs(board, i, j - 1, child, ans);
board[i][j] = c;
}
}
Python
class TrieNode:
def __init__(self):
self.children: Dict[str, TrieNode] = defaultdict(TrieNode)
self.word: Optional[str] = None
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m = len(board)
n = len(board[0])
ans = []
root = TrieNode()
def insert(word: str) -> None:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
for word in words:
insert(word)
def dfs(i: int, j: int, node: TrieNode) -> None:
if i < 0 or i == m or j < 0 or j == n:
return
if board[i][j] == '*':
return
c = board[i][j]
if c not in node.children:
return
child = node.children[c]
if child.word:
ans.append(child.word)
child.word = None
board[i][j] = '*'
dfs(i + 1, j, child)
dfs(i - 1, j, child)
dfs(i, j + 1, child)
dfs(i, j - 1, child)
board[i][j] = c
for i in range(m):
for j in range(n):
dfs(i, j, root)
return ans
Watch Tutorial
Checkout more Solutions here