Here, We see Word Search II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.
List of all LeetCode Solution
Word Search II LeetCode Solution
Table of Contents
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: []
Word Search II Leetcode Solution 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;
}
};
Code language: C++ (cpp)Word Search II Leetcode Solution 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;
}
}
Code language: Java (java)Word Search II Leetcode Solution 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;
}
};
Code language: JavaScript (javascript)Word Search II Leetcode Solution 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
Code language: Python (python)