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.
1import java.util.List;
2import java.util.ArrayList;
3import java.util.HashSet;
4import java.util.Set;
5
6class TrieNode {
7 TrieNode[] children;
8 String word;
9 public TrieNode() {
10 children = new TrieNode[26];
11 word = null;
12 }
13}
14
15public class Solution {
16 private void insertWord(TrieNode root, String word) {
17 TrieNode node = root;
18 for (char c : word.toCharArray()) {
19 if (node.children[c - 'a'] == null) {
20 node.children[c - 'a'] = new TrieNode();
21 }
22 node = node.children[c - 'a'];
23 }
24 node.word = word;
25 }
26
27 public List<String> findWords(char[][] board, String[] words) {
28 TrieNode root = new TrieNode();
29 for (String word : words) {
30 insertWord(root, word);
31 }
32 Set<String> result = new HashSet<>();
33 for (int i = 0; i < board.length; i++) {
34 for (int j = 0; j < board[0].length; j++) {
35 dfs(board, i, j, root, result);
36 }
37 }
38 return new ArrayList<>(result);
39 }
40
41 private void dfs(char[][] board, int i, int j, TrieNode node, Set<String> result) {
42 char c = board[i][j];
43 if (c == '#' || node.children[c - 'a'] == null) return;
44 node = node.children[c - 'a'];
45 if (node.word != null) {
46 result.add(node.word);
47 node.word = null;
48 }
49
50 board[i][j] = '#';
51 if (i > 0) dfs(board, i-1, j, node, result);
52 if (j > 0) dfs(board, i, j-1, node, result);
53 if (i < board.length - 1) dfs(board, i+1, j, node, result);
54 if (j < board[0].length - 1) dfs(board, i, j+1, node, result);
55 board[i][j] = c;
56 }
57}The Java solution creates a Trie from the words and then performs DFS on the board. Each character is examined, and its path is followed in the Trie structure. If a word is found, it's added to a result set, ensuring 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.
1public class Solution {
2 public bool Exist(char[][] board, string word) {
3 for (int i = 0; i < board.Length; i++) {
4 for (int j = 0; j < board[0].Length; j++) {
5 if (Dfs(board, word, i, j, 0, new bool[board.Length, board[0].Length])) {
6 return true;
7 }
8 }
9 }
10 return false;
11 }
12
13 private bool Dfs(char[][] board, string word, int i, int j, int index, bool[,] visited) {
14 if (index == word.Length) return true;
15 if (i < 0 || i >= board.Length || j < 0 || j >= board[0].Length) return false;
16 if (visited[i, j] || board[i][j] != word[index]) return false;
17
18 visited[i, j] = true;
19 if (Dfs(board, word, i + 1, j, index + 1, visited) ||
20 Dfs(board, word, i - 1, j, index + 1, visited) ||
21 Dfs(board, word, i, j + 1, index + 1, visited) ||
22 Dfs(board, word, i, j - 1, index + 1, visited)) {
23 return true;
24 }
25 visited[i, j] = false;
26 return false;
27 }
28}This C# implementation uses a grid search with a depth-first approach, utilizing a 2D array to track visited cells. By recursively exploring all directions, it determines the presence of the word on the board.