Last updated on January 20th, 2025 at 11:45 pm
Here, we see a Word Search II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Backtracking, Tree
Companies
Airbnb, Google, Microsoft
Level of Question
Hard
Word Search II LeetCode Solution
Table of Contents
1. Problem Statement
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: (fig-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: (fig-2) Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Trie + Backtracking”. Here’s how it works:
Backtracking: The algorithm explores all possible paths on the board using Depth-First Search (DFS) to find words that match the prefixes stored in the Trie.
Trie Construction: A Trie (prefix tree) is built to store all the words from the input list. This allows efficient prefix matching during the search.
3. Code Implementation in Different Languages
3.1 Word Search II C++
class Solution {
struct TrieNode {
TrieNode *children[26];
string word;
TrieNode() : word("") {
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
TrieNode *root = buildTrie(words);
vector<string> result;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
dfs(board, i, j, root, result);
}
}
return result;
}
TrieNode *buildTrie(vector<string> &words) {
TrieNode *root = new TrieNode();
for (int j = 0; j < words.size(); j++) {
string word = words[j];
TrieNode *curr = root;
for (int i = 0; i < word.length(); i++) {
char c = word[i] - 'a';
if (curr->children[c] == nullptr) {
curr->children[c] = new TrieNode();
}
curr = curr->children[c];
}
curr->word = word;
}
return root;
}
void dfs(vector<vector<char>> &board, int i, int j, TrieNode *p, vector<string> &result) {
char c = board[i][j];
if (c == '#' || !p->children[c - 'a']) return;
p = p->children[c - 'a'];
if (p->word.size() > 0) {
result.push_back(p->word);
p->word = "";
}
board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j, p, result);
if (j > 0) dfs(board, i, j - 1, p, result);
if (i < board.size() - 1) dfs(board, i + 1, j, p, result);
if (j < board[0].size() - 1) dfs(board, i, j + 1, p, result);
board[i][j] = c;
}
};
3.2 Word Search II Java
class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs (board, i, j, root, res);
}
}
return res;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
char c = board[i][j];
if (c == '#' || p.next[c - 'a'] == null) return;
p = p.next[c - 'a'];
if (p.word != null) { // found one
res.add(p.word);
p.word = null; // de-duplicate
}
board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j ,p, res);
if (j > 0) dfs(board, i, j - 1, p, res);
if (i < board.length - 1) dfs(board, i + 1, j, p, res);
if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
board[i][j] = c;
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null) p.next[i] = new TrieNode();
p = p.next[i];
}
p.word = w;
}
return root;
}
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}
}
3.3 Word Search II JavaScript
var findWords = function(board, words) {
const res = [], trie = {};
for (let word of words) {
let curNode = trie;
for (let char of word) {
curNode[char] = curNode[char] || {};
curNode[char].count = curNode[char].count + 1 || 1;
curNode = curNode[char];
};
curNode.end = word;
}
for (let row = 0; row < board.length; row++) {
for (let col = 0; col < board[row].length; col++) {
if (trie[board[row][col]]) traverse(row, col);
}
}
return res;
function traverse(row, col, node = trie) {
if (!board[row][col]) return;
const char = board[row][col], curNode = node[char];
if (!curNode) return;
if (curNode.end) {
res.push(curNode.end);
let toDelete = trie;
for (let char of curNode.end) {
toDelete[char].count--;
if (!toDelete[char].count) {
delete(toDelete[char]);
break;
}
toDelete = toDelete[char];
}
curNode.end = null;
}
board[row][col] = 0;
(col - 1 >= 0) && traverse(row, col - 1, curNode);
(col + 1 < board[row].length) && traverse(row, col + 1, curNode);
(row - 1 >= 0) && traverse(row - 1, col, curNode);
(row + 1 < board.length) && traverse(row + 1, col, curNode);
board[row][col] = char;
}
};
3.4 Word Search II Python
class Solution(object):
def findWords(self, board, words):
m, n = len(board), len(board[0])
dic = defaultdict(set)
for i in range(m):
for j in range(n):
dic[board[i][j]].add((i, j))
results = deque()
word, lngth, word_isReversed = '', 0, False
def dfs(cord, indx):
if indx == lngth:
if word_isReversed:
results.append(word[::-1])
else:
results.append(word)
return True
ch = word[indx]
i, j = cord
for cand in [(i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j)]:
if cand in dic[ch]:
dic[ch].remove(cand)
flag = dfs(cand, indx + 1)
dic[ch].add(cand)
if flag: return True
return False
ref = set()
for i in range(m):
for j in range(n - 1):
ref.add(board[i][j] + board[i][j + 1])
for j in range(n):
for i in range(m - 1):
ref.add(board[i][j] + board[i + 1][j])
def check(word):
for i in range(len(word) - 1):
if word[i] + word[i + 1] not in ref:
if word[i + 1] + word[i] not in ref:
return False
return True
for w in words:
if check(w):
if w[:4] == w[0]*4 or len(dic[w[-1]]) < len(dic[w[0]]):
word = w[::-1]
word_isReversed = True
else:
word = w
if word_isReversed: word_isReversed = False
lngth = len(word)
for cord in list(dic[word[0]]):
dic[word[0]].remove(cord)
flag = dfs(cord, 1)
dic[word[0]].add(cord)
if flag: break
return results
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(M * N * 4L + K * W) | O(K * W + M * N) |
| Java | O(M * N * 4L + K * W) | O(K * W + M * N) |
| JavaScript | O(M * N * 4L + K * W) | O(K * W + M * N) |
| Python | O(M * N * 4L + K * W) | O(K * W + M * N) |
where L is the length of the longest word, K is the number of words and W is the average word length.
- Time Complexity:
- Trie Construction: Building the Trie takes O(K * W), where
Kis the number of words andWis the average word length. - DFS Backtracking: For each cell in the board (M * N), the DFS explores up to 4 directions recursively, with a maximum depth of
L(the length of the longest word). This results in O(M * N * 4^L). - Total: O(M * N * 4^L + K * W).
- Trie Construction: Building the Trie takes O(K * W), where
- Space Complexity:
- Trie Storage: The Trie requires O(K * W) space to store all the words.
- Board Storage: The board itself takes O(M * N) space.
- Recursion Stack: The recursion stack for DFS can go up to a depth of
L, which is bounded by the longest word length. - Total: O(K * W + M * N).
- The code uses a Trie + Backtracking pattern to efficiently find all words from the list that can be formed on the board.
- The Trie enables fast prefix matching, while backtracking explores all possible paths on the board.
- The time complexity is dominated by the DFS traversal, and the space complexity is determined by the Trie and recursion stack.