Algorithm
Problem Name: 212. Word Search II
Problem Link: https://leetcode.com/problems/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.lengthn == board[i].length1 <= m, n <= 12board[i][j]is a lowercase English letter.1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i]consists of lowercase English letters.- All the strings of
wordsare unique.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct node_s {
struct node_s *child[26];
char *word;
} node_t;
typedef struct {
char **p;
int n;
int sz;
} res_t;
void add2res(res_t *res, char *word) {
if (res->sz == 0) {
res->sz = 10;
} else if (res->sz == res->n) {
res->sz *= 2;
}
res->p = realloc(res->p, res->sz * sizeof(char *));
//assert(res->p);
res->p[res->n ++] = word;
}
void add2trie(node_t *node, char *word) {
node_t *t;
char *p = word;
int k;
while (*p) {
k = *p - 'a';
t = node->child[k];
if (!t) {
t = calloc(1, sizeof(node_t));
//assert(t);
node->child[k] = t;
}
node = t;
p ++;
}
node->word = word;
}
void free_trie(node_t *node) {
int i;
node_t *t;
for (i = 0; i < 26; i ++) {
t = node->child[i];
if (t) {
free_trie(t);
}
}
free(node);
}
void dfs(char **board, int rowsz, int colsz, int x, int y, node_t *node, res_t *res) {
char c;
node_t *t;
int i, j, k;
const int offset[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
c = board[x][y];
// already visited
if (c == '.') return;
t = node->child[c - 'a'];
// not a match
if (!t) return;
// found a match
node = t;
if (node->word) {
add2res(res, node->word);
node->word = NULL; // done with this word
}
board[x][y] = '.';
for (k = 0; k < 4; k ++) {
i = x + offset[k][0];
j = y + offset[k][1];
if (i >= 0 && i < rowsz && j >= 0 && j < colsz) {
dfs(board, rowsz, colsz, i, j, node, res);
}
}
board[x][y] = c;
}
char** findWords(char** board, int boardRowSize, int boardColSize, char** words, int wordsSize, int* returnSize) {
res_t res = { 0 };
node_t *root;
int i, j;
root = calloc(1, sizeof(node_t));
//assert(root);
// build trie
for (i = 0; i < wordsSize; i ++) {
add2trie(root, words[i]);
}
// search
for (i = 0; i < boardRowSize; i ++) {
for (j = 0; j < boardColSize; j ++) {
dfs(board, boardRowSize, boardColSize, i, j, root, &res);
}
}
// free trie
free_trie(root);
*returnSize = res.n;
return res.p;
}
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"]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> findWords(vector<vector<char>>& board, vector < string>& words) {
vector<string>res;
unordered_map 0)
for(auto x: m[board[i][j]]){
bool found = false;
backtrack(board, 1, i, j, board.size(), board[0].size(), x, found);
if(found && find(res.begin(), res.end(), x) == res.end()) res.push_back(x);
}
return res;
}
void backtrack(vector<vector < char>>& board, int pos, int r, int c, int m, int n, string& word, bool& found){
if(board[r][c] == '0' || found) return;
if(pos == word.size()>{
found = true;
return;
}
char tmp = board[r][c];
board[r][c] = '0';
if(r - 1 >= 0 && board[r - 1][c] == word[pos]) backtrack(board, pos + 1, r - 1, c, m, n, word, found);
if(r + 1 < m && board[r + 1][c] == word[pos]) backtrack(board, pos + 1, r + 1, c, m, n, word, found);
if(c + 1 < n && board[r][c + 1] == word[pos]) backtrack(board, pos + 1, r, c + 1, m, n, word, found>;
if(c - 1 >= 0 && board[r][c - 1] == word[pos]) backtrack(board, pos + 1, r, c - 1, m, n, word, found);
board[r][c] = tmp;
}
};
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"]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
private final int[][] DIRS = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
public List < String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
for (Character letter : word.toCharArray()) {
if (node.children.containsKey(letter)) {
node = node.children.get(letter);
} else {
TrieNode newNode = new TrieNode();
node.children.put(letter, newNode);
node = newNode;
}
}
node.word = word;
}
List < String> result = new ArrayList<>();
for (int row = 0; row < board.length; ++row) {
for (int col = 0; col < board[row].length; ++col) {
if (root.children.containsKey(board[row][col])) {
backtracking(row, col, root, result, board);
}
}
}
return result;
}
private void backtracking(int row, int col, TrieNode parent, List < String> result, char[][] board) {
char letter = board[row][col];
TrieNode currNode = parent.children.get(letter);
if (currNode.word != null) {
result.add(currNode.word);
currNode.word = null;
}
board[row][col] = '#';
for (int[] dir : DIRS) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow < 0 || newRow >= board.length || newCol < 0 || newCol >= board[0].length) {
continue;
}
if (currNode.children.containsKey(board[newRow][newCol])) {
backtracking(newRow, newCol, currNode, result, board);
}
}
board[row][col] = letter;
if (currNode.children.isEmpty()) {
parent.children.remove(letter);
}
}
private class TrieNode {
Map < Character, TrieNode> children = new HashMap();
String word = null;
public TrieNode() {}
}
}
Input
board = [["a","b"],["c","d"]], words = ["abcb"]
Output
[]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
class Trie {
constructor() {
this.word = null
this.children = new Map()
}
add(word) {
let cur = this
for (let i = 0; i < word.length; i++) {
if (!cur.children.has(word[i])) {
cur.children.set(word[i], new Trie())
}
cur = cur.children.get(word[i])
}
cur.word = word
}
addArr(words) {
words.forEach(word => this.add(word))
}
}
const findWords = function(board, words) {
const trie = new Trie()
trie.addArr(words)
const results = []
const dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
dfs(board, i, j, trie, results, dirs)
}
}
return results
}
const dfs = (board, i, j, trie, results, dirs) => {
if(i < 0 || j < 0 || i >= board.length || j >= board[0].length) return
const char = board[i][j]
if (!trie.children.has(char)) return
const nextTrie = trie.children.get(char)
if (nextTrie.word) {
results.push(nextTrie.word)
nextTrie.word = null
}
for(let dir of dirs) {
board[i][j] = '#'
dfs(board, i + dir[0], j + dir[1], nextTrie, results, dirs)
board[i][j] = char
}
}
Input
board = [["a","b"],["c","d"]], words = ["abcb"]
Output
[]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findWords(self, board, words):
def explore(i, j, cur):
visited[i][j] = 0
if "#" in cur and cur["#"] not in res_set: res.append(cur["#"]); res_set.add(cur["#"])
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= x < m and 0 <= y < n and board[x][y] in cur and visited[x][y] == -1: explore(x, y, trie[cur[board[x][y]]])
visited[i][j] = -1
trie, cnt, m, n, res, res_set = {}, 1, len(board), len(board and board[0]), [], set()
visited, trie[0] = [[-1] * n for _ in range(m)], {}
for w in words:
cur = trie[0]
for c in w:
if c not in cur: trie[cnt], cur[c], cnt = {}, cnt, cnt + 1
cur = trie[cur[c]]
cur["#"] = w
for i in range(m):
for j in range(n):
if board[i][j] in trie[0]: explore(i, j, trie[trie[0][board[i][j]]])
return res
Input
board = [["a","b"],["c","d"]], words = ["abcb"]
Output
[]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0212_WordSearchII
{
public IList < string> FindWords(char[][] board, string[] words)
{
var result = new List();
var root = BuildTrie(words);
var N = board.Length;
var M = board[0].Length;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
BackTracking(board, i, j, N, M, root, result);
return result;
}
private void BackTracking(char[][] board, int i, int j, int N, int M, TrieNode node, IList < string> results)
{
var ch = board[i][j];
if (ch == '#' || node.Children[ch - 'a'] == null) return;
node = node.Children[ch - 'a'];
if (node.IsFinished)
{
results.Add(node.Word);
node.IsFinished = false;
}
board[i][j] = '#';
if (i > 0) BackTracking(board, i - 1, j, N, M, node, results);
if (j > 0) BackTracking(board, i, j - 1, N, M, node, results);
if (i < N - 1) BackTracking(board, i + 1, j, N, M, node, results);
if (j < M - 1) BackTracking(board, i, j + 1, N, M, node, results);
board[i][j] = ch;
}
private TrieNode BuildTrie(string[] words)
{
var root = new TrieNode();
foreach (var word in words)
{
var currentNode = root;
foreach (var ch in word)
{
if (currentNode.Children[ch - 'a'] == null)
currentNode.Children[ch - 'a'] = new TrieNode();
currentNode = currentNode.Children[ch - 'a'];
}
currentNode.IsFinished = true;
currentNode.Word = word;
}
return root;
}
public class TrieNode
{
public TrieNode[] Children { get; } = new TrieNode[26];
public bool IsFinished { get; set; }
public string Word { get; set; }
}
}
}
Input
board = [["a","b"],["c","d"]], words = ["abcb"]
Output
[]