LeetCode - 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 neighboring. The same letter cell may not be used more than once.

Problem statement taken from: https://leetcode.com/problems/word-search

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

Constraints

- m == board.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board and word consists of only lowercase and uppercase English letters.

Explanation

DFS algorithm

The movement across the m * n board is restricted to horizontal and vertical neighbors. So we can move only along four directions and not eight, since diagonal movement is restricted.

When we are pointing at a particular cell, we check if the word's 1st character matches the char in current cell. If yes, we match the next char of word in all the four directions of the current cell of grid. We continue doing this till we find the full word.

The way we navigate across the grid it resembles Depth First Search.

Let's check the algorithm:

// function main
- set x[4] = {1, -1, 0, 0}
      y[4] = {0, 0, 1, -1}

- initialize i and j

- loop for i = 0; i < board.size(); i++
  - loop for j = 0; j < board[0].size(); j++
    - if dfs(board, i, j, 0, word)
      - return true

// function dfs(board, i, j, position, word)
- if position >= word.size()
  - return true

// call resolvable function to check the boundary conditions of grid
// and see if the char at word position matches the board index board[i][j]
- if resolvable(board, i, j, position, word)
  - char t = board[i][j]
  - board[i][j] = '.'

  // if the current char matches we move across all the four directions to match the next char
  - loop for k = 0; k < 4; k++
    - if dfs(board, i + x[k], j + y[k], position + 1, word)
      - return true

  - board[i][j] = t

- return false

// function resolvable(board, i, j, position, word)
- return i >= 0 && i < board.size() && j >= 0 && j < board[0].size() && board[i][j] == word[position]

C++ solution

class Solution {
int x[4] = {1, -1, 0, 0};
int y[4] = {0, 0, 1, -1};

public:
bool resolvable(vector<vector<char>>& board, int i, int j, int position, string word){
    return (i >= 0 && i < board.size() && j >= 0 && j < board[0].size() && board[i][j] == word[position]);
}

public:
bool dfs(vector<vector<char>>& board, int i, int j, int position, string word){
    if(position >= word.size()){
        return true;
    }

    if(resolvable(board, i, j, position, word)){
        char t = board[i][j];
        board[i][j] = '.';
        for(int k = 0; k < 4; ++k){
            if(dfs(board, i + x[k], j + y[k], position + 1, word)){
                return true;
            }
        }

        board[i][j] = t;
    }

    return false;
}

public:
bool exist(vector<vector<char>>& board, string word) {
    int i, j;

    for(i = 0; i < board.size(); i++){
        for(j = 0; j < board[0].size(); j++){
            if(dfs(board, i, j, 0, word)){
                return true;
            }
        }
    }

    return false;
}
};

Golang solution

var x [4]int
var y [4]int

func resolvable(board [][]byte, i, j, position int, word string) bool {
    return i >= 0 && i < len(board) && j >= 0 && j < len(board[0]) && word[position] == board[i][j]
}

func dfs(board [][]byte, i, j, position int, word string) bool {
    if position >= len(word) {
        return true
    }

    if resolvable(board, i, j, position, word) {
        t := board[i][j]
        board[i][j] = '.'

        for k := 0; k < 4; k++ {
            if dfs(board, i + x[k], j + y[k], position + 1, word) {
                return true
            }
        }

        board[i][j] = t
    }

    return false
}

func exist(board [][]byte, word string) bool {
    x = [...]int{1, -1, 0, 0}
    y = [...]int{0, 0 , 1, -1}

    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if dfs(board, i, j, 0, word) {
                return true
            }
        }
    }

    return false
}

Javascript solution

var x = [1, -1, 0, 0];
var y = [0, 0, 1, -1];

function resolvable(board, i, j, position, word){
    return i >= 0 && i < board.length && j >= 0 && j < board[0].length && word[position] == board[i][j]
}

function dfs(board, i, j, position, word){
    if(position >= word.length) {
        return true;
    }

    if(resolvable(board, i, j, position, word)) {
        var t = board[i][j];
        board[i][j] = '.';

        for(var k = 0 ; k < 4; k++){
            if(dfs(board, i + x[k], j + y[k], position + 1, word)){
                return true;
            }
        }

        board[i][j] = t;
    }

    return false;
}

var exist = function(board, word) {
    for(var i = 0; i < board.length; i++){
        for(var j = 0; j < board[0].length; j++){
            if(dfs(board, i, j, 0, word)) {
                return true;
            }
        }
    }

    return false;
}

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: board = [['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']]
       word = 'SEE'

Step 1: initialize i, j

Step 2: loop for i = 0; i < board.size()
        0 < 3
        true

        loop for j = 0; j < board[0].size()
        0 < 4
        true

        dfs(board, i, j, 0, word)
        dfs(board, 0, 0, 0, word)

Step 3: //in function dfs
        if position >= word.size()
           0 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 0 >= 0 && 0 < 3 && j >= 0 && 0 < 4 && word[0] == board[0][0]
          - true && 'S' == 'A'
          - false

        return false

Step 4: We reach at step 2 and increment j
        i = 0
        j = 1

        dfs(board, i, j, 0, word)
        dfs(board, 0, 1, 0, word)

Step 5: //in function dfs
        if position >= word.size()
           0 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 0 >= 0 && 0 < 3 && 1 >= 0 && 1 < 4 && word[0] == board[0][1]
          - true && 'S' == 'B'
          - false

        return false

Step 6: We reach at step 2 and increment j
        i = 0
        j = 2

        dfs(board, i, j, 0, word)
        dfs(board, 0, 2, 0, word)

Step 7: //in function dfs
        if position >= word.size()
           0 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 0 >= 0 && 0 < 3 && 2 >= 0 && 2 < 4 && word[0] == board[0][2]
          - true && 'S' == 'C'
          - false

        return false

Step 8: We reach at step 2 and increment j
        i = 0
        j = 3

        dfs(board, i, j, 0, word)
        dfs(board, 0, 3, 0, word)

Step 9: //in function dfs
        if position >= word.size()
           0 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 0 >= 0 && 0 < 3 && 3 >= 0 && 3 < 4 && word[0] == board[0][3]
          - true && 'S' == 'E'
          - false

        return false

Step 10: We reach at step 2 and increment j
        i = 0
        j = 4

        dfs(board, i, j, 0, word)
        dfs(board, 0, 3, 0, word)

Step 11: //in function dfs
        if position >= word.size()
           0 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 0 >= 0 && 0 < 3 && 3 >= 0 && 4 < 4 && word[0] == board[0][3]
          - false && 'S' == 'E'
          - false

        return false

Step 12: We reach at step 2 and increment i and j is 0
        i = 1
        j = 0

        dfs(board, i, j, 0, word)
        dfs(board, 1, 0, 0, word)

Step 13: //in function dfs
        if position >= word.size()
           0 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 1 >= 0 && 1 < 3 && 0 >= 0 && 0 < 4 && word[0] == board[1][0]
          - true && 'S' == 'S'
          - true

          - t = board[i][j]
          - t = 'S'
          - board[i][j] = '.'
          - board[1][0] = '.'

          loop for k = 0; k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 1 + x[0], 0 + y[0], 0 + 1, word)
            - dfs(board, 1 + 1, 0 + 0, 0 + 1, word)
            - dfs(board, 2, 0 + 0, 1, word)

        // recursive call to dfs function
        if position >= word.size()
           1 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 2 >= 0 && 2 < 3 && 0 >= 0 && 0 < 4 && word[1] == board[2][0]
          - true && 'E' == 'A'
          - false


          k++
          k = 1

          loop for k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 1 + x[1], 0 + y[1], 0 + 1, word)
            - dfs(board, 1 - 1, 0 + 0, 0 + 1, word)
            - dfs(board, 0, 0, 1, word)

        // recursive call to dfs function
        if position >= word.size()
           1 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 0 >= 0 && 0 < 3 && 0 >= 0 && 0 < 4 && word[1] == board[0][0]
          - true && 'E' == 'A'
          - false

          k++
          k = 2

          loop for k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 1 + x[2], 0 + y[2], 0 + 1, word)
            - dfs(board, 1 + 0, 0 + 1, 0 + 1, word)
            - dfs(board, 1, 1, 1, word)

        // recursive call to dfs function
        if position >= word.size()
           1 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 1 >= 0 && 1 < 3 && 1 >= 0 && 1 < 4 && word[1] == board[1][1]
          - true && 'E' == 'F'
          - false

          k++
          k = 3

          loop for k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 1 + x[3], 0 + y[3], 0 + 1, word)
            - dfs(board, 1 + 0, 0 - 1, 0 + 1, word)
            - dfs(board, 1, -1, 1, word)

        // recursive call to dfs function
        if position >= word.size()
           1 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 1 >= 0 && 1 < 3 && -1 >= 0 && 1 < 4 && word[1] == board[1][1]
          - false

          k++
          k = 4

          loop for k < 4
            - false

        return false

Step 14: We reach at step 2 and increment i and j is 0
        i = 1
        j = 1

        dfs(board, i, j, 0, word)
        dfs(board, 1, 1, 0, word)

        This is false since word[0] != board[1][1]
        'S' != 'F'

Step 15: We reach at step 2 and increment i and j is 1
        i = 1
        j = 2

        dfs(board, i, j, 0, word)
        dfs(board, 1, 2, 0, word)

        This is false since word[0] != board[1][2]
        'S' != 'C'

Step 16: We reach at step 2 and increment i and j is 2
        i = 1
        j = 3

        dfs(board, i, j, 0, word)
        dfs(board, 1, 3, 0, word)

Step 17: //in function dfs
        if position >= word.size()
           0 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 1 >= 0 && 1 < 3 && 3 >= 0 && 3 < 4 && word[0] == board[1][3]
          - true && 'S' == 'S'
          - true

          - t = board[i][j]
          - t = 'S'
          - board[i][j] = '.'
          - board[1][3] = '.'

          loop for k = 0; k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 1 + x[0], 3 + y[0], 0 + 1, word)
            - dfs(board, 1 + 1, 3 + 0, 0 + 1, word)
            - dfs(board, 2, 3, 1, word)

        // recursive call to dfs function
        if position >= word.size()
           1 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 2 >= 0 && 2 < 3 && 3 >= 0 && 3 < 4 && word[1] == board[2][3]
          - true && 'E' == 'E'
          - true

          - t = board[i][j]
          - t = 'E'
          - board[i][j] = '.'
          - board[2][3] = '.'

          loop for k = 0; k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 2 + x[0], 3 + y[0], 1 + 1, word)
            - dfs(board, 2 + 1, 3 + 0, 2, word)
            - dfs(board, 3, 3, 1, word)

        // recursive call to dfs function
        if position >= word.size()
           2 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 3 >= 0 && 3 < 3 && 3 >= 0 && 3 < 4 && word[2] == board[2][3]
          - false && 'E' == 'E'
          - false

          k++
          k = 1

          loop for k = 0; k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 2 + x[1], 3 + y[1], 1 + 1, word)
            - dfs(board, 2 - 1, 3 + 0, 2, word)
            - dfs(board, 1, 3, 2, word)

        // recursive call to dfs function
        if position >= word.size()
           2 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 1 >= 0 && 1 < 3 && 3 >= 0 && 3 < 4 && word[2] == board[1][3]
          - false && 'E' == 'C'
          - false

          k++
          k = 2

          loop for k = 0; k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 2 + x[2], 3 + y[2], 1 + 1, word)
            - dfs(board, 2 + 0, 3 + 1, 2, word)
            - dfs(board, 2, 4, 2, word)

        // recursive call to dfs function
        if position >= word.size()
           2 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 2 >= 0 && 2 < 3 && 4 >= 0 && 4 < 4 && word[2] == board[2][4]
          - false

          k++
          k = 3

          loop for k = 0; k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 2 + x[3], 3 + y[3], 1 + 1, word)
            - dfs(board, 2 + 0, 3 - 1, 2, word)
            - dfs(board, 2, 2, 2, word)

        // recursive call to dfs function
        if position >= word.size()
           2 >= 3
           false

        if resolvable(board, i, j, position, word)
          - i >= 0 && i < board.size() && j >= 0 && j < board[0].size && word[position] == board[i][j]
          - 2 >= 0 && 2 < 3 && 2 >= 0 && 2 < 4 && word[2] == board[2][2]
          - true && 'E' == 'E'
          - true

          - t = board[i][j]
          - t = 'E'
          - board[i][j] = '.'
          - board[2][2] = '.'

          loop for k = 0; k < 4
            - dfs(board, i + x[k], j + y[k], position + 1, word)
            - dfs(board, 2 + x[0], 2 + y[0], 2 + 1, word)
            - dfs(board, 2 + 1, 2 + 0, 3, word)
            - dfs(board, 2, 2, 3, word)

        // recursive call to dfs function
        if position >= word.size()
           3 >= 3
           true

Step 18: // Here we have covered all chars of the string 'SEE' and found in the grid.
         // So we return true from this recursive calls and return to exist function.

So the answer we return is true.