Description:
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.
Examples:
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: falseSolution in Python:
To solve the problem of finding if a word exists in a grid by traversing sequentially adjacent cells (either horizontally or vertically), we can use Depth-First Search (DFS) with backtracking.
Approach:
- Initialize Variables:
- Define the directions for moving in the grid: up, down, left, right.
- Get the dimensions of the board (number of rows and columns).
- Backtracking Function:
- This function will recursively check each cell to see if it matches the current character of the word.
- If the current character matches, continue to the next character by moving to adjacent cells.
- If all characters are matched, return
True. - If the current path does not lead to a solution, backtrack by marking the cell as unvisited and trying another path.
- Main Function:
- Iterate through each cell in the grid.
- For each cell, start the backtracking process.
- If any starting point leads to a successful match, return
True.
- Boundary Conditions:
- Ensure the current cell is within the grid bounds.
- Ensure the current cell has not been visited in the current path.
Python
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# Define the directions for moving in the grid
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# Get the dimensions of the board
rows, cols = len(board), len(board[0])
def backtrack(r, c, index):
# If the current character matches the last character of the word, return True
if index == len(word):
return True
# If the current cell is out of bounds or doesn't match the current character, return False
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]:
return False
# Mark the cell as visited by changing its value
temp = board[r][c]
board[r][c] = '#'
# Explore all possible directions
for dr, dc in directions:
if backtrack(r + dr, c + dc, index + 1):
return True
# Unmark the cell as visited (backtrack)
board[r][c] = temp
return False
# Iterate through each cell in the grid
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return FalseExplanation:
- Function
exist:- Initializes the directions for moving in the grid.
- Gets the dimensions of the board.
- Defines the
backtrackfunction which will be used to explore all possible paths. - Iterates through each cell in the grid and starts the backtracking process from each cell.
- Returns
Trueif any starting point leads to finding the word, otherwise returnsFalse.
- Function
backtrack:- Checks if the current index matches the length of the word, indicating the word has been fully matched.
- Checks if the current cell is out of bounds or does not match the current character of the word.
- Marks the current cell as visited by changing its value to
#. - Explores all four possible directions (up, down, left, right) and recursively calls
backtrack. - Unmarks the cell by restoring its original value (backtracking).
- Returns
Trueif any path leads to a match, otherwise returnsFalse.
This implementation ensures that all possible paths are explored while avoiding revisiting cells in the current path, making it efficient for the given constraints.
Solution in Javascript:
JavaScript
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
// Define the directions for moving in the grid
const directions = [
[0, 1], // right
[1, 0], // down
[0, -1], // left
[-1, 0] // up
];
// Get the dimensions of the board
const rows = board.length;
const cols = board[0].length;
function backtrack(r, c, index) {
// If the current character matches the last character of the word, return true
if (index === word.length) {
return true;
}
// If the current cell is out of bounds or doesn't match the current character, return false
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[index]) {
return false;
}
// Mark the cell as visited by changing its value
const temp = board[r][c];
board[r][c] = '#';
// Explore all possible directions
for (let [dr, dc] of directions) {
if (backtrack(r + dr, c + dc, index + 1)) {
return true;
}
}
// Unmark the cell as visited (backtrack)
board[r][c] = temp;
return false;
}
// Iterate through each cell in the grid
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (backtrack(r, c, 0)) {
return true;
}
}
}
return false;
};Solution in Java:
Java
class Solution {
// Directions arrays to explore up, down, left, and right neighbors
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public boolean exist(char[][] board, String word) {
// Edge case: if the board or word is empty, return false
if (board == null || board.length == 0 || word == null || word.length() == 0) {
return false;
}
int rows = board.length;
int cols = board[0].length;
// Start the search from each cell in the grid
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (backtrack(board, word, row, col, 0)) {
return true;
}
}
}
return false; // If no path matches the word, return false
}
private boolean backtrack(char[][] board, String word, int row, int col, int index) {
// Base case: if the entire word is matched
if (index == word.length()) {
return true;
}
// Check if the current position is out of bounds or the character does not match
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != word.charAt(index)) {
return false;
}
// Mark the cell as visited by temporarily changing its value
char temp = board[row][col];
board[row][col] = '#';
// Explore all possible directions
for (int[] direction : DIRECTIONS) {
int newRow = row + direction[0];
int newCol = col + direction[1];
if (backtrack(board, word, newRow, newCol, index + 1)) {
return true;
}
}
// Restore the cell's original value before returning
board[row][col] = temp;
return false;
}
}Solution in C#:
C#
public class Solution {
// Directions arrays to explore up, down, left, and right neighbors
private static readonly int[][] DIRECTIONS = new int[][] {
new int[] { 0, 1 }, // Right
new int[] { 1, 0 }, // Down
new int[] { 0, -1 }, // Left
new int[] { -1, 0 } // Up
};
public bool Exist(char[][] board, string word) {
// Edge case: if the board or word is empty, return false
if (board == null || board.Length == 0 || word == null || word.Length == 0) {
return false;
}
int rows = board.Length;
int cols = board[0].Length;
// Start the search from each cell in the grid
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (Backtrack(board, word, row, col, 0)) {
return true;
}
}
}
return false; // If no path matches the word, return false
}
private bool Backtrack(char[][] board, string word, int row, int col, int index) {
// Base case: if the entire word is matched
if (index == word.Length) {
return true;
}
// Check if the current position is out of bounds or the character does not match
if (row < 0 || row >= board.Length || col < 0 || col >= board[0].Length || board[row][col] != word[index]) {
return false;
}
// Mark the cell as visited by temporarily changing its value
char temp = board[row][col];
board[row][col] = '#';
// Explore all possible directions
foreach (var direction in DIRECTIONS) {
int newRow = row + direction[0];
int newCol = col + direction[1];
if (Backtrack(board, word, newRow, newCol, index + 1)) {
return true;
}
}
// Restore the cell's original value before returning
board[row][col] = temp;
return false;
}
}