This approach uses a Trie to represent the list of words for efficient prefix matching. The algorithm performs depth-first search (DFS) on the board starting from each cell. Each path of exploration is checked against the Trie to determine if it forms any of the words or prefixes thereof. The benefit of using a Trie is that we can stop the search early if the current path does not match any prefix in the Trie, thereby improving the efficiency of the search process.
Time Complexity: O(M*(4*3^(L-1))), where M is the number of cells on the board, and L is the maximum length of a word.
Space Complexity: O(N*L), where N is the number of words, and L is the maximum length of a word, used by the Trie structure.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include <string.h>
5
6#define ALPHABET_SIZE 26
7
8typedef struct TrieNode {
9 struct TrieNode* children[ALPHABET_SIZE];
10 char* word;
11} TrieNode;
12
13TrieNode* createTrieNode() {
14 TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
15 for (int i = 0; i < ALPHABET_SIZE; i++)
16 node->children[i] = NULL;
17 node->word = NULL;
18 return node;
19}
20
21void insertWord(TrieNode* root, char* word) {
22 TrieNode* node = root;
23 while (*word) {
24 if (!node->children[*word - 'a'])
25 node->children[*word - 'a'] = createTrieNode();
26 node = node->children[*word - 'a'];
27 word++;
28 }
29 node->word = strdup(word);
30}
31
32void findWordsDFS(char** board, int i, int j, int m, int n, TrieNode* node, bool** visited, char** result, int* returnSize) {
33 if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || !node->children[board[i][j] - 'a'])
34 return;
35
36 node = node->children[board[i][j] - 'a'];
37 if (node->word) {
38 result[*returnSize] = strdup(node->word);
39 (*returnSize)++;
40 node->word = NULL; // Avoid duplicate printing
41 }
42
43 visited[i][j] = true;
44 findWordsDFS(board, i + 1, j, m, n, node, visited, result, returnSize);
45 findWordsDFS(board, i - 1, j, m, n, node, visited, result, returnSize);
46 findWordsDFS(board, i, j + 1, m, n, node, visited, result, returnSize);
47 findWordsDFS(board, i, j - 1, m, n, node, visited, result, returnSize);
48 visited[i][j] = false;
49}
50
51char** findWords(char** board, int boardSize, int* boardColSize, char** words, int wordsSize, int* returnSize) {
52 TrieNode* root = createTrieNode();
53 for (int i = 0; i < wordsSize; i++)
54 insertWord(root, words[i]);
55
56 *returnSize = 0;
57 char** result = (char**)malloc(1000 * sizeof(char*)); // Assumption on max result size
58 bool** visited = (bool**)malloc(boardSize * sizeof(bool*));
59 for (int i = 0; i < boardSize; i++)
60 visited[i] = (bool*)calloc(*boardColSize, sizeof(bool));
61
62 for (int i = 0; i < boardSize; i++) {
63 for (int j = 0; j < *boardColSize; j++) {
64 findWordsDFS(board, i, j, boardSize, *boardColSize, root, visited, result, returnSize);
65 }
66 }
67
68 // Free visited array
69 for (int i = 0; i < boardSize; i++)
70 free(visited[i]);
71 free(visited);
72
73 return result;
74}This C solution constructs a Trie for the list of words and uses a recursive DFS to explore each board cell. During the exploration, it checks for word matches and adds them to the result if found. The Trie structure is dynamically built using a set of Trie nodes. The DFS ensures not to visit the same cell multiple times within the same exploration path.
In this approach, we perform backtracking for each word individually. This avoids the overhead of constructing a Trie but involves repeated board scanning. A Recursive Depth First Search (DFS) is used to explore possibilities starting from each cell on the board. We maintain a visited matrix to ensure a letter is not reused in forming a particular word.
Time Complexity: O(N * M * 3^L), where N is the number of words, M is the number of cells in the board, and L is the length of the word being searched in the worst case.
Space Complexity: O(L), for the recursive call stack.
1class Solution:
2 def exist(self, board, word):
3 def dfs(i, j, index):
4 if index == len(word):
5 return True
6 if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
7 return False
8 if board[i][j] != word[index]:
9 return False
10 tmp, board[i][j] = board[i][j], '#' # mark visited
11 found = (dfs(i+1, j, index+1) or
12 dfs(i-1, j, index+1) or
13 dfs(i, j+1, index+1) or
14 dfs(i, j-1, index+1))
15 board[i][j] = tmp # unmark visited
16 return found
17
18 for i in range(len(board)):
19 for j in range(len(board[0])):
20 if dfs(i, j, 0):
21 return True
22 return FalseIn this Python version, the dfs function tries to match each character in the word on the board. By marking visited nodes with a temporary replacement, it facilitates recursion without repeating nodes within the same word search.