Word Search Using Backtracking Algorithm

Introduction

 

We all have played Word Search but what if we build a code which would actually search a word and return whether it exists or not? This can be achieved by one very simple and elegant algorithmic technique known as the backtracking algorithm. We choose the backtracking algorithm because it's deterministic and goes in a depth-first order, at each level we can edit information, which keeps the state of our system the way we need it to for the next level's recursive calls, and then we can undo the change we made for whenever we go back up to the previous level. In short, we can have shared variable without having to create a new one for each recursive call which in turn, saves time as well as memory. So in this article we will discuss how to search a given word in a given N x N board using the backtracking algorithm.

 

Problem Statement

 

Given a 2D board of characters and a word to search, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Given below are the sample inputs and their outputs respectively for the problem. For more details, here is the link to the leetcode question.

static void Main(string[] args)
{
    var game = new WordSearch(new List<List<char>>{
        new List<char>{'A', 'B', 'C', 'E'},
        new List<char>{'S', 'F', 'C', 'S'},
        new List<char>{'A', 'D', 'E', 'E'}
    });
    var result = game.Exist("ABCCED"); // true
    result = game.Exist("SEE"); // true
    result = game.Exist("ABCB"); // false
}

Solution

 

We are allowed to start from any block in the board, can only travel to adjacent (i.e., up, down, left & right) blocks and cannot reuse any block. Considering these three conditions as our golden rules now we will construct our algorithm by iterating over every block in the board and in each iteration we will perform the following,

1. Check if the block is valid, as in whether it's out of bounds or whether the searching word has the character or not.
2. Mark the current block with any other character which manages the 3rd golden rule of the problem (cannot reuse any block), we have used '#'.
3. Now we will recursively check the left, right, up and down blocks to match the next character of the searching word.
4. Unmark the block which we had marked in step 2.
5. Return true if this block was the end of the word or else any of the recursive calls returned true.

So here is the C# code for the solution to this problem,

class WordSearch
{
    private readonly List<List<char>> Board;
    public WordSearch(List<List<char>> board)
    {
        this.Board = board;
    }
    private bool ExistCharacter(int i, int j, int searchIndex, string searchWord)
    {
        // when reached outside the board
        if (i< 0 || i >= Board.Count || j< 0 || j >= Board[i].Count)
            return false;

        // when index character does not match
        if(Board[i][j] != searchWord[searchIndex])
            return false;

        // when completely matched
        if(searchIndex == searchWord.Length - 1)
            return true;

        // mark the current character
        Board[i][j] = '#';

        // check every direction
        bool found = ExistCharacter(i, j - 1, searchIndex + 1, searchWord) ||
            ExistCharacter(i, j + 1, searchIndex + 1, searchWord) ||
            ExistCharacter(i - 1, j, searchIndex + 1, searchWord) ||
            ExistCharacter(i + 1, j, searchIndex + 1, searchWord);

        // unmark the current character
        Board[i][j] = searchWord[searchIndex];
        return found;
    }
    public bool Exist(string searchWord)
    {
        if (searchWord == "")
            return false;

        // iterate over the board
        for (int i = 0; i < Board.Count; i++)
        {
            for (int j = 0; j < Board[i].Count; j++)
            {
                // check first character
                if (ExistCharacter(i, j, 0, searchWord))
                    return true;
            }
        }
        return false;
    }
}