Word Search Ii

                                            
class TrieNode {
public:
    vector<TrieNode*> children;
    string word;
    
    TrieNode(): children(26), word("") {}
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> result;
        TrieNode* root = buildTrie(words);
        
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                dfs(board, i, j, root, result);
            }
        }
        
        return result;
    }
    
    TrieNode* buildTrie(vector<string>& words) {
        TrieNode* root = new TrieNode();
        
        for (string word : words) {
            TrieNode* node = root;
            for (char c : word) {
                int index = c - 'a';
                if (!node->children[index]) {
                    node->children[index] = new TrieNode();
                }
                node = node->children[index];
            }
            node->word = word;
        }
        
        return root;
    }
    
    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, vector<string>& result) {
        char c = board[i][j];
        if (c == '#' || !node->children[c - 'a']) {
            return;
        }
        
        node = node->children[c - 'a'];
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word = "";
        }
        
        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j, node, result);
        if (j > 0) dfs(board, i, j - 1, node, result);
        if (i < board.size() - 1) dfs(board, i + 1, j, node, result);
        if (j < board[0].size() - 1) dfs(board, i, j + 1, node, result);
        board[i][j] = c;
    }
};

                                            
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        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 void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
        char c = board[i][j];
        if (c == '#' || node.next[c - 'a'] == null) return;
        
        node = node.next[c - 'a'];
        if (node.word != null) {
            result.add(node.word);
            node.word = null;
        }
        
        board[i][j] = '#';
        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);
        board[i][j] = c;
    }
    
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.next[index] == null) {
                    node.next[index] = new TrieNode();
                }
                node = node.next[index];
            }
            node.word = word;
        }
        return root;
    }
    
    class TrieNode {
        TrieNode[] next;
        String word;
        
        TrieNode() {
            next = new TrieNode[26];
            word = null;
        }
    }
}

                                            
class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        """
        def dfs(board, i, j, word):
            if len(word) == 0:
                return True
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]:
                return False
            tmp, board[i][j] = board[i][j], '#'
            res = dfs(board, i + 1, j, word[1:]) or dfs(board, i - 1, j, word[1:]) or dfs(board, i, j + 1, word[1:]) or dfs(board, i, j - 1, word[1:])
            board[i][j] = tmp
            return res
        
        result = set()
        for word in words:
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if dfs(board, i, j, word):
                        result.add(word)
        return list(result)

To solve this coding challenge, we need to identify all the words from the given list that can be found on the provided board of characters. The words can be formed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. Each cell cannot be reused within the same word construction.

Explanation

The problem essentially requires a combination of a depth-first search (DFS) algorithm and backtracking. Here’s a detailed breakdown of the solution:

Initialization and Setup : We need to initialize the board and words list, and setup the necessary variable to keep track of words that are found.
Depth-First Search (DFS) : For each cell in the board, perform a DFS to explore all possible paths that can form the words from the given list. The DFS will recursively check each adjacent cell (up, down, left, right) while ensuring no cell is reused in the current word’s construction.
Backtracking : During the DFS, temporarily mark the current cell as visited by replacing its character with a placeholder. After exploring all paths from the current cell, revert it back to its original state to allow reuse in other word constructions starting from different cells.
Result Collection : Use a set to collect words that are found during the DFS exploration to avoid duplicates.
Output : Convert the set of found words into a list and return as the result.

Below is the pseudocode with detailed comments on each step:

                                            
# Pseudocode with Explanation

# Perform Depth-First Search on the board to find the word
Function DFS(board, i, j, word):
# If all letters in the word are successfully matched
If length of word is 0:
Return True

# If out of board boundaries or letter does not match
If i < 0 OR i >= number of rows in board OR j < 0 OR j >= number of columns in board OR board[i][j] != word[0]:
Return False

# Mark the current cell as visited by placing a temporary marker
temp = board[i][j]
board[i][j] = '#'

# Recursively search the adjacent cells (up, down, left, right) for the next letter in the word
result = DFS(board, i + 1, j, word[1:]) OR  # Down
DFS(board, i - 1, j, word[1:]) OR  # Up
DFS(board, i, j + 1, word[1:]) OR  # Right
DFS(board, i, j - 1, word[1:])     # Left

# Revert the current cell to its original character
board[i][j] = temp

Return result

# Main Function to find all words in the board
Function findWords(board, words):
# Initialize a set to store found words to prevent duplicates
found_words = Set()

# Iterate through each word in the words list
For each word in words:
# Iterate through each cell in the board
For i from 0 to number of rows in board:
For j from 0 to number of columns in board:
# If the word is found starting from cell (i, j), add it to the found_words set
If DFS(board, i, j, word):
Add word to found_words

# Convert set of found words to a list and return
Return List(found_words)

Step-by-Step Explanation / Detailed Steps in Pseudocode

Initialization :

Create a function
DFS

that will handle the recursive depth-first search for word matching.
Create a main function
findWords

to iterate over each word in the input list and each cell in the board.

Depth-First Search (DFS) :

For the
DFS

function, check if the current cell is out of boundaries or if the current cell's character does not match the next character in the word.
If the conditions are met for being out of boundaries or character mismatch, return
False

.
If all characters of the word have been matched (
length of word == 0

), return
True

.
Temporarily mark the current cell as visited by changing its character to
'#'

.
Recursively call the
DFS

function on all adjacent cells (up, down, left, right).
Restore the current cell's character after exploring all paths from it.

Backtracking :

Restore the visited cell back to its original character after exploring all adjacent cells in the current DFS path.

Result Collection :

Use a set to store and prevent duplicate words found during the exploration.

Output :

Convert the set of found words into a list and return it.

This approach ensures that all possible paths are evaluated for forming words while maintaining efficiency and correctness through the use of DFS and backtracking.