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:
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 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[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:
    vector findWords(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" }; 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[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; } }