Word Search

shriyanshi24jindal

Mar 30th, 2026

130

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 9.11 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/**
We try to match the word character by character by exploring neighbors.
At any cell (i, j):
- If it matches word[index], we try all 4 directions
- Move to next index (index + 1)
- If path fails → backtrack
*/
public boolean exist(char[][] board, String word) {
int n = board.length;
int m = board[0].length;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(dfs(board, word, i, j, 0))
return true;
}
}
return false;
}
public boolean dfs(char[][] board, String word, int row, int col, int index)
{
int n = board.length;
int m = board[0].length;
// base case
if(index == word.length())
return true;
// invalid case
if(row < 0 || col < 0 || row >= n || col >= m || board[row][col] != word.charAt(index))
{
return false;
}
// mark visited
char temp = board[row][col];
board[row][col] = '#';
// explore all 4-directions
boolean result = dfs(board, word, row+1, col, index+1) ||
dfs(board, word, row, col+1, index+1) ||
dfs(board, word, row-1, col, index+1) ||
dfs(board, word, row, col-1, index+1);
// backtrack
board[row][col] = temp;
return result;
}
}

RAW Paste Data Copied

class Solution {
    /**
    We try to match the word character by character by exploring neighbors.
    At any cell (i, j):
        - If it matches word[index], we try all 4 directions
        - Move to next index (index + 1)
        - If path fails → backtrack
    */
    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;

for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(dfs(board, word, i, j, 0)) 
                    return true;
            }
        }
        return false;
    }

public boolean dfs(char[][] board, String word, int row, int col, int index)
    {
        int n = board.length;
        int m = board[0].length;

// base case
        if(index == word.length())
            return true;

// invalid case
        if(row < 0 || col < 0 || row >= n || col >= m || board[row][col] != word.charAt(index)) 
        {
            return false;
        }

// mark visited
        char temp = board[row][col];
        board[row][col] = '#';
        
        // explore all 4-directions
        boolean result = dfs(board, word, row+1, col, index+1) ||
                         dfs(board, word, row, col+1, index+1) ||
                         dfs(board, word, row-1, col, index+1) ||
                         dfs(board, word, row, col-1, index+1);

// backtrack
        board[row][col] = temp;
        return result;
    }
}