To optimize the performance of the word search solver, we can implement a few techniques. The word search problem can have multiple solutions, so to improve efficiency, we can stop the search as soon as we find the first valid solution. This can be achieved by updating the isWordExist function to return a boolean value indicating if the word was found.
Additionally, we can apply pruning techniques to eliminate unnecessary search branches. One approach is to pre-process the word and grid to identify word patterns that are impossible to exist. For example, if the grid does not contain any of the characters in the word, we can immediately return false without performing the search. Similarly, if the word contains duplicate characters and the grid does not have multiple occurrences of those characters, we can also return false.
Furthermore, we can optimize the search process by using heuristics. Instead of starting the search from the first cell of the grid, we can analyze the grid and prioritize cells that are more likely to contain the first character of the word. This can be based on the frequency of characters in the grid or their proximity to other found words.
Here's an optimized C++ implementation of the word search solver:
1#include <iostream>
2#include <vector>
3using namespace std;
4
5bool isWordExist(vector<vector<char>>& grid, string word, int row, int col, int index) {
6 int n = grid.size();
7 int m = grid[0].size();
8
9 // Base cases
10 if (index == word.size()) {
11 return true; // Word found
12 }
13
14 if (row < 0 || row >= n || col < 0 || col >= m || grid[row][col] != word[index]) {
15 return false; // Current cell doesn't match the character
16 }
17
18 // Mark the current cell as visited
19 char temp = grid[row][col];
20 grid[row][col] = '#';
21
22 // Explore the neighboring cells
23 bool found = isWordExist(grid, word, row, col + 1, index + 1) ||
24 isWordExist(grid, word, row, col - 1, index + 1) ||
25 isWordExist(grid, word, row + 1, col, index + 1) ||
26 isWordExist(grid, word, row - 1, col, index + 1);
27
28 // Restore the cell
29 grid[row][col] = temp;
30
31 return found;
32}
33
34bool wordSearch(vector<vector<char>>& grid, string word) {
35 int n = grid.size();
36 int m = grid[0].size();
37
38 // Preprocessing
39 // Count frequency of characters in word
40 vector<int> charFreq(26, 0);
41 for (char c : word) {
42 charFreq[c - 'A']++;
43 }
44
45 // Check if the grid contains any of the characters in the word
46 for (int i = 0; i < n; i++) {
47 for (int j = 0; j < m; j++) {
48 if (charFreq[grid[i][j] - 'A'] > 0) {
49 goto startSearch;
50 }
51 }
52 }
53 return false; // Word not found
54
55 startSearch:
56
57 // Iterate over each cell in the grid
58 for (int i = 0; i < n; i++) {
59 for (int j = 0; j < m; j++) {
60 if (grid[i][j] == word[0]) {
61 // Check if the word exists starting from this cell
62 if (isWordExist(grid, word, i, j, 0)) {
63 return true; // Word found
64 }
65 }
66 }
67 }
68
69 return false; // Word not found
70}
71
72int main() {
73 // Grid representing the word search puzzle
74 vector<vector<char>> grid = {
75 {'A', 'B', 'C'},
76 {'F', 'I', 'N'},
77 {'T', 'O', 'R'}
78 };
79
80 // Word to be searched
81 string word = "BIT";
82
83 // Check if the word exists in the grid
84 bool exists = wordSearch(grid, word);
85
86 // Print the result
87 if (exists) {
88 cout << "The word \"" << word << "\" exists in the grid." << endl;
89 } else {
90 cout << "The word \"" << word << "\" does not exist in the grid." << endl;
91 }
92
93 return 0;
94}xxxxxxxxxx}using namespace std;bool isWordExist(vector<vector<char>>& grid, string word, int row, int col, int index) { int n = grid.size(); int m = grid[0].size(); // Base cases if (index == word.size()) { return true; // Word found } if (row < 0 || row >= n || col < 0 || col >= m || grid[row][col] != word[index]) { return false; // Current cell doesn't match the character } // Mark the current cell as visited char temp = grid[row][col]; grid[row][col] = '#'; // Explore the neighboring cells bool found = isWordExist(grid, word, row, col + 1, index + 1) || isWordExist(grid, word, row, col - 1, index + 1) || isWordExist(grid, word, row + 1, col, index + 1) || isWordExist(grid, word, row - 1, col, index + 1); // Restore the cell grid[row][col] = temp;