# Solution For Word Search Ii

Problem Statement:

Given an m x n grid of words board and a list of 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: []

Approach:

The problem can be solved using the Trie data structure (Trie is a tree-like data structure that stores a dynamic set of strings). We create a Trie from the list of words provided in the input. Once we have the Trie, we can search for all valid words on the board by traversing the board and Trie simultaneously.

Steps:

1. Create a Trie from the list of words given in the input. Each node of the Trie will store:
2. the character at the current node
3. a boolean flag to indicate whether the current node represents the end of a word from the input list
4. a list of children nodes
5. Traverse the board and for each cell in the board, search for all valid words that can be formed starting from that cell.
6. For each cell in the board, perform a depth-first traversal, following all possible paths that can be formed starting from that cell on the board.
7. If at any point during the traversal, we reach a dead end (i.e., the current path does not match any word in the Trie), we backtrack and explore other possible paths.
8. If we reach a Trie node that represents the end of a word from the input list, add that word to the final list of valid words.
9. Return the final list of valid words.

Code:

Here is the Python code to solve the Word Search II problem using the Trie data structure:

class TrieNode:
def init(self):
self.char = None
self.end_of_word = False
self.children = {}

class Trie:
def init(self):
self.root = TrieNode()

``````def add_word(self, word):
current_node = self.root
for char in word:
if char not in current_node.children:
current_node.children[char] = TrieNode()
current_node = current_node.children[char]
current_node.end_of_word = True
``````

class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
if not board or not words:
return [] trie = Trie()
for word in words:
m, n = len(board), len(board)
visited = set()
res = set()

``````    def dfs(i, j, current_node, prefix):
# check if current node is end of a word
if current_node.end_of_word:
# mark current cell as visited
# explore all possible paths from the current cell
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
x, y = i + dx, j + dy
# check if new cell is within bounds and not visited already
if 0 <= x < m and 0 <= y < n and (x, y) not in visited and board[x][y] in current_node.children:
dfs(x, y, current_node.children[board[x][y]], prefix + board[x][y])
# backtrack
visited.remove((i, j))

for i in range(m):
for j in range(n):
if board[i][j] in trie.root.children:
dfs(i, j, trie.root.children[board[i][j]], board[i][j])

return list(res)
``````

Time Complexity:

The time complexity of the above solution is O(m x n x 4^k), where m is the number of rows in the board, n is the number of columns in the board, and k is the maximum length of words in the input list. The reason for 4^k is that for each cell in the board, we have at most 4 possible neighbors to explore, and we can explore up to k cells in a single path. Therefore, the worst-case scenario is when all cells in the board are explored, and we have to search for all words of length k in the Trie.

## Step by Step Implementation For Word Search Ii

```class Solution {
public List findWords(char[][] board, String[] words) {
List result = new ArrayList<>();
// edge case
if (board == null || board.length == 0 || words == null || words.length == 0) {
return result;
}
// create a Trie to store all the words
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.word = word;
}
// search for words in the board
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
dfs(board, i, j, root, result);
}
}
return result;
}
// use dfs to search for words in the board
public void dfs(char[][] board, int i, int j, TrieNode node, List result) {
char c = board[i][j];
if (c == '#' || node.children[c - 'a'] == null) {
return;
}
node = node.children[c - 'a'];
// found a word
if (node.word != null) {
// de-duplicate
node.word = null;
}
// mark the current cell as visited
board[i][j] = '#';
// explore the neighbors in 4 directions
if (i > 0) {
dfs(board, i - 1, j, node, result);
}
if (j > 0) {
dfs(board, i, j - 1, node, result);
}
if (i < board.length - 1) {
dfs(board, i + 1, j, node, result);
}
if (j < board.length - 1) {
dfs(board, i, j + 1, node, result);
}
// reset the cell
board[i][j] = c;
}
// TrieNode class
class TrieNode {
TrieNode[] children = new TrieNode;
String word;
}
}```
```class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
```This problem can be solved with a brute force approach, where we check every word in the list against every cell in the board. However, this is not very efficient, as it has a time complexity of O(mn * w), where m is the number of rows in the board, n is the number of columns in the board, and w is the number of words in the list.

A more efficient approach would be to use a trie, which is a data structure that stores words in a tree-like structure. We can use a trie to store all of the words in the list, and then we can use it to quickly check if a word is in the list. This approach is much faster, as it has a time complexity of O(mn + w).

var findWords = function(board, words) {
// Create a trie to store all of the words in the list
var root = createTrie(words);

// Keep track of all of the words that we find
var foundWords = [];

// Loop through every cell in the board
for (var i = 0; i < board.length; i++) {
for (var j = 0; j < board[i].length; j++) {
// Check if the cell contains a word
checkCell(i, j, board, root, foundWords);
}
}

return foundWords;
};

function checkCell(i, j, board, trie, foundWords) {
// Get the character at the cell
var c = board[i][j];

// If the character is not in the trie, then there is no word that starts with this character
if (!(c in trie)) {
return;
}

// Mark the cell as visited
board[i][j] = "#";

// Check if this is a word
if ("isWord" in trie[c]) {
foundWords.push(trie[c].word);
}

// Check the cells around this one
if (i > 0) {
checkCell(i - 1, j, board, trie[c], foundWords);
}
if (j > 0) {
checkCell(i, j - 1, board, trie[c], foundWords);
}
if (i < board.length - 1) {
checkCell(i + 1, j, board, trie[c], foundWords);
}
if (j < board[i].length - 1) {
checkCell(i, j + 1, board, trie[c], foundWords);
}

// Mark the cell as unvisited
board[i][j] = c;
}

function createTrie(words) {
// Create the root node
var root = {};

// Loop through all of the words
for (var i = 0; i < words.length; i++) {
// Get the word
var word = words[i];

// Add the word to the trie
}

return root;
}

// Loop through each character in the word
for (var i = 0; i < word.length; i++) {
// Get the character
var c = word[i];

// If the character is not in the trie, add it
if (!(c in trie)) {
trie[c] = {};
}

// Move to the next character in the trie
trie = trie[c];
}

// Mark the end of the word
trie.isWord = true;

// Store the word
trie.word = word;
}```
```class Solution {
public:
vector findWords(vector>& board, vector& words) {
`using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { char[][] board = new char[][] { new char[] { 'o', 'a', 'a', 'n' }, new char[] { 'e', 't', 'a', 'e' }, new char[] { 'i', 'h', 'k', 'r' }, new char[] { 'i', 'f', 'l', 'v' } }; string[] words = new string[] { "oath", "pea", "eat", "rain" }; List result = FindWords(board, words); foreach (string word in result) { Console.WriteLine(word); } Console.ReadLine(); } public static List FindWords(char[][] board, string[] words) { List result = new List(); if (board == null || board.Length == 0 || words == null || words.Length == 0) { return result; } TrieNode root = BuildTrie(words); for (int i = 0; i < board.Length; i++) { for (int j = 0; j < board.Length; j++) { DFS(board, i, j, root, result); } } return result; } private static void DFS(char[][] board, int i, int j, TrieNode p, List result) { char c = board[i][j]; if (c == '#' || p.next[c - 'a'] == null) { return; } p = p.next[c - 'a']; if (p.word != null) // found one { result.Add(p.word); p.word = null; // de-duplicate } 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.Length - 1) { DFS(board, i + 1, j, p, result); } if (j < board.Length - 1) { DFS(board, i, j + 1, p, result); } board[i][j] = c; } private static TrieNode BuildTrie(string[] words) { TrieNode root = new TrieNode(); foreach (string word in words) { TrieNode p = root; for (int i = 0; i < word.Length; i++) { int index = word[i] - 'a'; if (p.next[index] == null) { p.next[index] = new TrieNode(); } p = p.next[index]; } p.word = word; } return root; } } class TrieNode { public TrieNode[] next = new TrieNode; public String word; } }`