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 <vector>
2#include <string>
3#include <unordered_set>
4using namespace std;
5
6class TrieNode {
7public:
8 vector<TrieNode*> children;
9 string word;
10 TrieNode() : children(26, nullptr), word("") {}
11};
12
13class Solution {
14 void insertWord(TrieNode* root, const string& word) {
15 TrieNode* node = root;
16 for (char ch : word) {
17 if (!node->children[ch - 'a']) {
18 node->children[ch - 'a'] = new TrieNode();
19 }
20 node = node->children[ch - 'a'];
21 }
22 node->word = word;
23 }
24
25 void dfs(vector<vector<char>>& board, int i, int j, TrieNode* node, unordered_set<string>& result) {
26 char ch = board[i][j];
27 if (ch == '#' || !node->children[ch - 'a']) return;
28 node = node->children[ch - 'a'];
29 if (!node->word.empty()) {
30 result.insert(node->word);
31 node->word.clear(); // Avoid duplicates
32 }
33
34 board[i][j] = '#'; // Mark visited
35 if (i > 0) dfs(board, i - 1, j, node, result);
36 if (j > 0) dfs(board, i, j - 1, node, result);
37 if (i < board.size() - 1) dfs(board, i + 1, j, node, result);
38 if (j < board[0].size() - 1) dfs(board, i, j + 1, node, result);
39 board[i][j] = ch; // Reset
40 }
41
42public:
43 vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
44 TrieNode* root = new TrieNode();
45 for (const string& word : words) {
46 insertWord(root, word);
47 }
48
49 unordered_set<string> result;
50 for (int i = 0; i < board.size(); i++) {
51 for (int j = 0; j < board[0].size(); j++) {
52 dfs(board, i, j, root, result);
53 }
54 }
55 return vector<string>(result.begin(), result.end());
56 }
57};The C++ solution builds a Trie for the words and utilizes DFS to explore the board. It marks cells as visited by temporarily setting them to '#' and resets them after backtracking. Found words are added to a hash set to manage duplicates efficiently.
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.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4
5bool dfs(char** board, int boardSize, int boardColSize, char* word, int index, int i, int j, bool** visited) {
6 if (index == strlen(word)) return true;
7 if (i < 0 || i >= boardSize || j < 0 || j >= boardColSize || visited[i][j] || board[i][j] != word[index])
8 return false;
9
10 visited[i][j] = true;
11 if (dfs(board, boardSize, boardColSize, word, index + 1, i - 1, j, visited) ||
12 dfs(board, boardSize, boardColSize, word, index + 1, i + 1, j, visited) ||
13 dfs(board, boardSize, boardColSize, word, index + 1, i, j - 1, visited) ||
14 dfs(board, boardSize, boardColSize, word, index + 1, i, j + 1, visited)) {
15 return true;
16 }
17 visited[i][j] = false;
18 return false;
19}
20
21bool exist(char** board, int boardSize, int* boardColSize, char* word) {
22 bool** visited = (bool**)malloc(boardSize * sizeof(bool*));
23 for (int i = 0; i < boardSize; i++) {
24 visited[i] = (bool*)calloc(*boardColSize, sizeof(bool));
25 }
26 for (int i = 0; i < boardSize; i++) {
27 for (int j = 0; j < *boardColSize; j++) {
28 if (dfs(board, boardSize, *boardColSize, word, 0, i, j, visited)) {
29 for (int k = 0; k < boardSize; k++){
30 free(visited[k]);
31 }
32 free(visited);
33 return true;
34 }
35 }
36 }
37 for (int i = 0; i < boardSize; i++){
38 free(visited[i]);
39 }
40 free(visited);
41 return false;
42}This C solution attempts to find each word on the board individually. We use a helper function dfs that tries to construct the word by moving to adjacent cells recursively. The solution checks for existence of a path for each word, returning as soon as one is found.