79. Word Search

Hello, reader 👋🏽 ! Welcome to day 54 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 79. Word Search.

🤔 Problem Statement

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 neighbouring. The same letter cell may not be used more than once.
E.g.:

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"
=> true

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCB" 
=> false

💬 Thought Process - Depth First Search + Backtracing

We can approach this problem similar to a graph problem where we check for characters in the word along neighbours of a cell.
The board is traversed from the beginning. Whenever there's a match between the first character in the word and character in the board, we recursively try to search all the neighbours beginning from this cell until we find all the characters in the word.
The neighbours of a cell needs to be searched recursively. We'll maintain three indices for:
- board row
- board column
- string index
From every index (row, col), we'll search for (row-1, col), (row+1, col), (row, col-1), and (row, col+1).
Whenever we search a cell, we'll mark the cell in the board as visited by changing the character to '.'. This is to ensure that we don't visit a cell twice in the same iteration.
Once the cell's neighbours have been searched for, we'll perform backtracking and unmark the cell by assigning it back to the original character.
Since the search method would happen recursively, our base cases would be:
- Base case 1: Whenever index of the string is equal to the length of the string, it means all the characters in the board have been found, return true.
- Base case 2: If the board indices are out of bounds or the cell has been visited, return false.
- Base case 3: If the character in the cell is not equal to character in the string at index, return false.
If either of the neighbouring calls returns true, the word has been found.

👩🏽‍💻 Solution - Depth First Search + Backtracing

Below is the code for the above explained approach.

class Solution {
  private int m, n;
  public boolean exist(char[][] board, String word) {
      if(board == null || board.length == 0) return false;

      m = board.length;
      n = board[0].length;

      for(int row = 0; row < m; row++) {
          for(int col = 0; col < n; col++) {
              char firstCh = word.charAt(0);
              if(board[row][col] == firstCh) {
                  if(search(board, word, row, col, 0)) {
                      return true;
                  }
              }
          }
      }

      return false;
  }

  private boolean search(char[][] board, String word, 
int row, int col, int index) {
      int len = word.length();
      if(index >= len) {
          return true;
      }

      if(row < 0 || row >= m || col < 0 || 
        col >= n || board[row][col] == '.') {
          return false;
      }

      char ch = board[row][col];
      char wordCh = word.charAt(index);

      if(ch != wordCh)  return false;

      board[row][col] = '.';

      boolean ans = search(board, word, row-1, col, index+1) || 
          search(board, word, row+1, col, index+1) || 
          search(board, word, row, col-1, index+1) ||
          search(board, word, row, col+1, index+1);

      board[row][col] = ch;
      return ans;
  }
}

Time Complexity: O(m * n * 4 ^ len(word))
- m = number of rows in board
- n = number of columns in board
- word = given input word
Space Complexity: O(len(word))
- Stack space used that could be maximum length of the word

You can find the link to the GitHub repo for this question here: 79. Word Search.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian