LeetCode: Word Search in 2D Matrix of characters

Difficulty Level: $\mathtt{MEDIUM}$
This is a LeetCode question. Find the DESCRIPTION HERE

Solution

This problem can be solved using Depth First Search (DFS) which will employ necessary Backtracking. Starting from any cell, we look for a match of characters from the beginning of input word. If there is a match, we look for the next character in the input word in the neighboring unvisited cells of the board. When the whole word is found, we return true.

Backtracking

When there is a match for a character in a word, we move to next character and also move to next neighbor. For the given cell there are Four possible neighbors. At a time, we select one neighbor and expand the search. It can happen that one neighbor might lead to a path where only some characters are matched while other neighbor can lead to the path where whole word is matched. So if we select the first neigbor, it will ultimately lead the end where we don't have any match. At such time, we should be able to backtrack and follow different path to look for possible desirable path.

Implementation

Following is the implemenation of the backtracking solution using DFS discussed above.

	/* File: WordSearch.java
	* Created: 9/19/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 WorldLingo Inc.
	*/
	//=======================================================================================
	/**
	* @author Sabbir Manandhar manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class WordSearch {
	/**
	* Verifies if the given word can be found in the given board by moving left, right, top and bottom
	* unvisited cells of the board.
	* @param board Given board.
	* @param word Given word.
	* @return True if the word is found in the board, False otherwise.
	*/
	public boolean exist(char[][] board, String word) {
	int ROW = board.length;
	int COL = board[0].length;
	for (int row = 0; row < ROW; row++) {
	for (int col = 0; col < COL; col++) {
	if (dfs(board, new boolean[ROW][COL], word, 0, row, col, ROW, COL)) return true;
	}
	}
	return false;
	} // exist
	//-------------------------------------------------------------------------------------
	/**
	* Searches for the occurrence of characters in given word from the position <code>cursor</code>
	* in the given 2D board starting from given row and col.
	*
	* @param board Input 2D board of characters
	* @param visited Visited characters in the cell
	* @param word Given input word
	* @param cursor current location in the given word
	* @param row current row in the board
	* @param col current column in the board
	* @param ROW number of Rows in the board
	* @param COLUMN number of Columns in the board
	* @return True if the word occurs in the board, False otherwise
	*/
	public boolean dfs(char[][] board, boolean[][] visited, String word, int cursor, int row, int col, int ROW, int COLUMN) {
	if (cursor == word.length()) return true;
	if (!inBoard(row, col, ROW, COLUMN)) return false;
	if (visited[row][col]) return false;
	if (board[row][col] == word.charAt(cursor)) {
	visited[row][col] = true;
	boolean exist = dfs(board, visited, word, cursor + 1, row + 1, col, ROW, COLUMN) ||
	dfs(board, visited, word, cursor + 1, row, col + 1, ROW, COLUMN) ||
	dfs(board, visited, word, cursor + 1, row - 1, col, ROW, COLUMN) ||
	dfs(board, visited, word, cursor + 1, row, col - 1, ROW, COLUMN);
	if (exist) return true;
	visited[row][col] = false;
	} else {
	return false;
	}
	return false;
	} // dfs
	//-------------------------------------------------------------------------------------
	/**
	* Verify if given row and column are withing the limit
	* @param row given row
	* @param col given column
	* @param ROW ROW limit
	* @param COLUMN Column limit
	* @return True if the row and column are within the limit, False otherwise
	*/
	private boolean inBoard(int row, int col, int ROW, int COLUMN) {
	return row >= 0 && row < ROW && col >= 0 && col < COLUMN;
	} // inBoard
	} // WordSearch

view raw WordSearch.java hosted with ❤ by GitHub

Time Complexity

The exist() method runs two loops for $row \times column$ times and the dfs() method can also run upto $row \times column$ times.
$\therefore$ The complexity of this approach is $\cal{O(mn)^2}$ where $m\ = \ number\ of\ rows$ and $n\ = \ number\ of\ columns$.

Space Complexity

Here we are using extra 2D matrix visited to keep track of cells which are already visited.
$\therefore$The space complexity is $\cal{O(mn)}$.
This can be reduced to $\cal{O(1)}$ by modifying the input board to update each character with special character to mark that it has been visited. The modified character can be reset afterwards.

---

---

---