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:
- Create a Trie from the list of words given in the input. Each node of the Trie will store:
- the character at the current node
- a boolean flag to indicate whether the current node represents the end of a word from the input list
- a list of children nodes
- Traverse the board and for each cell in the board, search for all valid words that can be formed starting from that cell.
- 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.
- 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.
- 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.
- 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:
trie.add_word(word)
m, n = len(board), len(board[0])
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:
res.add(prefix)
# mark current cell as visited
visited.add((i, j))
# 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 ListfindWords(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[0].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) { result.add(node.word); // 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[0].length - 1) { dfs(board, i, j + 1, node, result); } // reset the cell board[i][j] = c; } // TrieNode class class TrieNode { TrieNode[] children = new TrieNode[26]; String word; } }
class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: # Your code here
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 addWord(word, root); } return root; } function addWord(word, trie) { // 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: vectorfindWords(vector >& board, vector & words) { // Your code here } };
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" }; Listresult = 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[0].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[0].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[26]; public String word; } }