Word Search Board Editorial

Practice Problem Link: Word Search Board

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a board of size n*m, containing an English alphabet in each cell. You are also given a word, find if the word exists on the board. The word can be constructed from letters of sequentially adjacent cells. Cells which have a common edge are considered adjacent. The same cell may not be used more than once.

Approach

We can model this into a DFS on-grid problem. We start from the 1st character of the word to find as root and recursively traverse to adjacent valid cells to find the next character of the word. When we find the whole word, we return true, else after checking all possible cases, we return false.

Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(1)

Implementation

C++

bool wordSearch(vector<vector<char>>& board, string word, int i, int j, int index) {
	if(index == word.size()) {
		return true;
	}
	int n = board.size();
	int m = board[0].size();
	if(i < 0 || j < 0 || i >= n || j >= m) {
		return false;
	}
	if(board[i][j] != word[index]) {
		return false;
	}
	bool returnValue = wordSearch(board, word, i + 1, j, index + 1);
	returnValue |= wordSearch(board, word, i - 1, j, index + 1);
	returnValue |= wordSearch(board, word, i, j + 1, index + 1);
	returnValue |= wordSearch(board, word, i, j - 1, index + 1);
	return returnValue;
}
bool wordExists(vector<vector<char>> board, string word) {
    int wordLen = word.size();
	if(wordLen == 0) {
		return true;
	}
	int n = board.size();
	int m = board[0].size();
	if(n == 0 || m == 0) {
		return 0;
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(board[i][j] == word[0]) {
				if(wordSearch(board, word, i, j, 0)) {
					return true;
				}
			}
		}
	}
	return false;
}

Java

class Solution {
	boolean wordSearch(char[][] board, String word, int i, int j, int index) {
		if(index == word.length()) {
			return true;
		}
		int n = board.length;
		int m = board[0].length;
		if(i < 0 || j < 0 || i >= n || j >= m) {
			return false;
		}
		if(board[i][j] != word.charAt(index)) {
			return false;
		}
		boolean returnValue = wordSearch(board, word, i + 1, j, index + 1);
		returnValue |= wordSearch(board, word, i - 1, j, index + 1);
		returnValue |= wordSearch(board, word, i, j + 1, index + 1);
		returnValue |= wordSearch(board, word, i, j - 1, index + 1);
		return returnValue;
	}
	boolean wordExists(char[][] board, String word) {
    	int wordLen = word.length();
		if(wordLen == 0) {
			return true;
		}
		int n = board.length;
		int m = board[0].length;
		if(n == 0 || m == 0) {
			return false;
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if((board[i][j] - 'A') == (word.charAt(0) - 'A')) {
					if(wordSearch(board, word, i, j, 0)) {
						return true;
					}
				}
			}
		}
		return false;
	}
}