In the Leetcode Word Search problem solution 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.
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.
Solution in C Programming
bool search_word(char** board, int x, int y, char* word, bool* previous, int index);
bool not_in(int x, int y, int* previous, int m, int n);
// global variables for the board size
int m, n;
bool exist(char** board, int boardSize, int* boardColSize, char* word){
m = boardSize;
n = *boardColSize;
// set a 2d array, the size of the board for our previously visited cells
bool *previous = (bool *)malloc(sizeof(bool) * boardSize * *boardColSize);
memset(previous, 0, m * n);
// iterate over the board
for (int x = 0; x < m; x++){
for (int y = 0; y < n; y++){
if (board[x][y] == word[0])
{
// if the word is 1 character long, return true
if (strlen(word) == 1)
{
return true;
}
if (search_word(board, x, y, word, previous, 0))
{
return true;
}
}
}
}
return false;
}
/*
function for checking whether the coordinates are on the board
*/
bool onBoard(int x, int y)
{
if (x >= 0 && y >= 0 && x < m && y < n)
{
return true;
}
return false;
}
/*
function for recursively looking for the next letters in our word
*/
bool search_word(char** board, int x, int y, char* word, bool* previous, int index)
{
// when the whole string has been found, return true
if (index == strlen(word))
{
return true;
}
// neighbour coordinates
int x_off[4] = {-1, 1, 0, 0};
int y_off[4] = {0, 0, -1, 1};
if (!onBoard(x, y))
{
return false;
}
bool path = false;
// if the offset is the character we are looking for, and the cell has not been used yet
if (board[x][y] == word[index] && !previous[x * n + y])
{
// add the current cell to the previously visited cells
previous[x * n + y] = true;
// loop over all offsets [above, below, left, right]
for (int i = 0; i < 4; i++)
{
int new_x = x + x_off[i];
int new_y = y + y_off[i];
if (search_word(board, new_x, new_y, word, previous, index + 1))
{
path = true;
}
}
// if the rest of the word cannot be found here, delete cell from memory
if (!path)
{
previous[x * n + y] = false;
}
}
return path;
}Solution in C++ Programming
class Solution {
int dirx[4] = {-1,1,0,0};
int diry[4] = {0,0,-1,1};
int n, m;
bool DFS(vector<vector<char>>& board, int i, int j, vector<vector<int>> &visited, string &word, int idx)
{
if(idx == word.size()) return true;
if(i >= n || i < 0 || j >= m || j < 0) return false;
if(visited[i][j] == 1) return false;
if(board[i][j] != word[idx]) return false;
visited[i][j] = 1;
int nxtx, nxty;
for(int x = 0; x < 4; x++)
{
nxtx = i + dirx[x];
nxty = j + diry[x];
if(DFS(board, nxtx, nxty, visited, word, idx+1))
return true;
}
visited[i][j] = 0;
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
n = board.size();
m = board[0].size();
vector<vector<int>> visited(n, vector<int> (m,0));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(DFS(board, i, j, visited, word, 0))
return true;
}
}
return false;
}
};Solution in Java Programming
class Solution {
public boolean exist(char[][] board, String word) {
int m=board.length;
int n=board[0].length;
//calling function for all chars of grid as we need to search the starting point from where the word starts.
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(helper(i,j,board,word,0))
return true;
}
}
return false;
}
private boolean helper(int i,int j,char[][] board, String word,int l){
if(l==word.length())//when we have traversed all chars of word.
return true;
if(i<0 ||j<0 ||i>=board.length||j>=board[0].length||board[i][j]!=word.charAt(l))
return false;
char temp=board[i][j];
board[i][j]=' ';//for marking visted char in board
//if we have found same char at any location we return true.
if( helper(i-1,j,board,word,l+1)||
helper(i+1,j,board,word,l+1)||
helper(i,j+1,board,word,l+1)||
helper(i,j-1,board,word,l+1))
return true;
board[i][j]=temp;//backtracking step undo the changes done before the recursive calls if we have not found any ans so far for that row.
return false;
}
}Solution in Python Programming
class Solution:
def exist(self, board, word):
m,n = len(board),len(board[0])
def checkpath(i,j,Index):
if Index == len(word)-1:
return True
for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
if 0<=x<m and 0<=y<n:
if board[x][y] == word[Index+1]:
if (x,y) not in Table:
Table.add((x,y))
if checkpath(x,y,Index+1):
return True
Table.remove((x,y))
return False
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
Table = set()
Table.add((i,j))
if checkpath(i,j,0):
return True
return FalseSolution in C# Programming
public class Solution
{
public bool Exist(char[][] board, string word)
{
if (board == null || board.Length == 0 || string.IsNullOrEmpty(word)) return false;
bool wordExists = false;
for (int i = 0; i < board.Length; i++)
{
for (int j = 0; j < board[0].Length; j++)
{
if (board[i][j] == word[0] && !wordExists)
{
wordExists = DFS(board, i, j, word);
}
}
}
return wordExists;
}
private bool DFS(char[][] board, int i, int j, string word)
{
if (string.IsNullOrEmpty(word)) return true;
if (board == null || i < 0 || i >= board.Length || j < 0 || j >= board[0].Length || board[i][j] != word[0]) return false;
char temp = board[i][j];
board[i][j] = ' ';
var found = DFS(board, i, j + 1, word.Substring(1)) ||
DFS(board, i, j - 1, word.Substring(1)) ||
DFS(board, i + 1, j, word.Substring(1)) ||
DFS(board, i - 1, j, word.Substring(1));
board[i][j] = temp;
return found;
}
}Also read,