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.
1using System;
2using System.Collections.Generic;
3
4public class TrieNode {
5 public TrieNode[] Children = new TrieNode[26];
6 public string Word;
7}
8
9public class Solution {
10 public IList<string> FindWords(char[][] board, string[] words) {
11 TrieNode root = new TrieNode();
12 foreach (var word in words) InsertWord(root, word);
13 HashSet<string> result = new HashSet<string>();
14 for (int i = 0; i < board.Length; i++)
15 for (int j = 0; j < board[0].Length; j++)
16 Dfs(board, i, j, root, result);
17 return new List<string>(result);
18 }
19
20 private void InsertWord(TrieNode root, string word) {
21 TrieNode node = root;
22 foreach (var ch in word) {
23 if (node.Children[ch - 'a'] == null)
24 node.Children[ch - 'a'] = new TrieNode();
25 node = node.Children[ch - 'a'];
26 }
27 node.Word = word;
28 }
29
30 private void Dfs(char[][] board, int i, int j, TrieNode node, HashSet<string> result) {
31 char c = board[i][j];
32 if (c == '#' || node.Children[c - 'a'] == null) return;
33 node = node.Children[c - 'a'];
34 if (node.Word != null) {
35 result.Add(node.Word);
36 node.Word = null; // Avoid duplicates
37 }
38
39 board[i][j] = '#';
40 if (i > 0) Dfs(board, i - 1, j, node, result);
41 if (j > 0) Dfs(board, i, j - 1, node, result);
42 if (i < board.Length - 1) Dfs(board, i + 1, j, node, result);
43 if (j < board[0].Length - 1) Dfs(board, i, j + 1, node, result);
44 board[i][j] = c;
45 }
46}The C# solution constructs a Trie for input words and performs DFS on the board. The Trie is traversed according to characters found during the DFS. A hash set gathers the found words to ensure uniqueness.
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.
1function exist(board, word) {
2 function dfs(i, j, index) {
3 if (index === word.length) return true;
4 if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
5 if (board[i][j] !== word[index]) return false;
6 let temp = board[i][j];
7 board[i][j] = '#';
8 let found = dfs(i+1, j, index+1) ||
9 dfs(i-1, j, index+1) ||
10 dfs(i, j+1, index+1) ||
11 dfs(i, j-1, index+1);
12 board[i][j] = temp;
13 return found;
14 }
15
16 for (let i = 0; i < board.length; i++) {
17 for (let j = 0; j < board[0].length; j++) {
18 if (dfs(i, j, 0)) return true;
19 }
20 }
21 return false;
22}This JavaScript solution checks the possibility of forming the word by executing DFS from each cell. By temporarily changing the board values, it prevents reusing the same cell during the formation of a word.