79. Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” Output: true

Example 2:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE” Output: true

Example 3:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB” Output: false

Solution §

Naive Approach (Spaghetti Code) §

 
bool searchLetter(vector < vector <char> >& grid, string& s, int x, int y, int s_pos, char prev){
  char chr = s[s_pos+1];
  int last = s.length();
  int nxt_pos = s_pos + 1;
  bool ans = false;
  cout << "FInding " << chr << ' ' <<  prev <<  endl ; 
  // Search Right
  if ((x+1) < grid.size() && grid[x+1][y] == chr && prev != 'd'){
    cout << s[nxt_pos] << " Found at " << x+1 << ' ' << y << endl;
    ans = searchLetter(grid, s, x+1, y, nxt_pos, 'u');
    if (ans){
      return true;
    }
  }
  if ((x-1) >= 0 && grid[x-1][y] == chr && prev != 'u'){
    cout << s[nxt_pos] << " Found at " << x-1 << ' ' << y << endl;
    ans = searchLetter(grid, s, x-1, y, nxt_pos, 'd');
    if (ans){
      return true;
    }
  } 
  if ((y+1) < grid[x].size() && grid[x][y+1] == chr && prev != 'r' ){
    cout << s[nxt_pos] << " Found at " << x << ' ' << y+1 << endl;
    ans = searchLetter(grid, s, x, y+1, nxt_pos, 'l');
    if (ans){
      return true;
    }
  } 
  if ((y-1) >= 0 && grid[x][y-1] == chr && prev != 'l'){
    cout << s[nxt_pos] << " Found at " << x << ' ' << y-1 << endl;
    ans = searchLetter(grid, s, x, y-1, nxt_pos, 'r');
    if (ans){
      return true;
    }
  } 
  if ((nxt_pos) == last){
    cout << "EXECUTED" << endl;
    return true;
  }
 
  return ans;
};
 
  bool exist(vector<vector<char>>& board, string word) {
    bool ans = false;
    bool search = false;
    for (int i = 0; i < board.size(); i++){
      int s_ps = 0;
        for (int j = 0; j < board[i].size(); j++){
        if (board[i][j] == word[s_ps]){
            cout << "First letter " << word[s_ps]  << i << ' ' << j << endl;
            search = searchLetter(board, word, i, j, s_ps, '-');
      }
      if (search){
        ans = true;
      }
    }
  }
  return ans;
    }
 

Modified and Simpler Approach §

using namespace std;
 
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == word[0] && searchLetter(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
 
private:
    bool searchLetter(vector<vector<char>>& grid, string& s, int x, int y, int s_pos) {
        if (s_pos == s.length()) {
            return true; // All characters found
        }
 
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[x].size() || grid[x][y] != s[s_pos]) {
            return false; // Out of bounds or mismatch
        }
 
        char original = grid[x][y];
        grid[x][y] = '-'; // Mark the cell as visited
 
        bool found = searchLetter(grid, s, x + 1, y, s_pos + 1) ||
                     searchLetter(grid, s, x - 1, y, s_pos + 1) ||
                     searchLetter(grid, s, x, y + 1, s_pos + 1) ||
                     searchLetter(grid, s, x, y - 1, s_pos + 1);
 
        grid[x][y] = original; // Restore the original value
        return found;
    }
};

1. Moved the searchLetter function into the Solution class as a private member function.
2. Removed the ‘prev’ parameter and the direction checks (‘u’, ‘d’, ‘l’, ‘r’) since it’s not necessary for this backtracking approach.
3. Checked whether you have found the entire word by comparing s_pos to the length of the word.
4. Marked visited cells with a temporary marker (’-’) and restored them to their original state after backtracking. This prevents revisiting the same cell during the search.
5. Simplified the exist function to start the search from all possible positions and return true if the word is found.

This should work as expected to find a word in the 2D grid using backtracking.

The way we use DFS is by going in depth first to figure out if xyz is true or false meaning it is run recursively until all the instances of the stack function are found to be true, when this happens the chain leading up to that point all trigger to be true giving the correct answer as either valid or invalid. And in order to prevent backtracking we change the instance of that position in the array to be something other than a movable pattern