Algorithm

Problem Name: 212. 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.

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];

if (c == '.') return;

t = node->child[c - 'a'];

// not a match
if (!t) return;

// found a match
node = t;

if (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 ++) {
}

// 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;
}
``````
Copy The Code &

Input

cmd
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]

Output

cmd
["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;
}
};
``````
Copy The Code &

Input

cmd
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]

Output

cmd
["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) {
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() {}
}
}
``````
Copy The Code &

Input

cmd
board = [["a","b"],["c","d"]], words = ["abcb"]

Output

cmd
[]

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
class Trie {
constructor() {
this.word = null
this.children = new Map()
}
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
}
}
}

const findWords = function(board, words) {
const trie = new Trie()
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
}

}
``````
Copy The Code &

Input

cmd
board = [["a","b"],["c","d"]], words = ["abcb"]

Output

cmd
[]

#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
``````
Copy The Code &

Input

cmd
board = [["a","b"],["c","d"]], words = ["abcb"]

Output

cmd
[]

#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)
{
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; }
}
}
}
``````
Copy The Code &

Input

cmd
board = [["a","b"],["c","d"]], words = ["abcb"]

Output

cmd
[]