4950515253545556575859606162636465

package main

import (
	"fmt"
)

// Helper function to check if the word exists starting from cell (i, j)
func dfs(board [][]byte, i, j int, word string, k int) bool {
	// If all characters of the word are found
	if k == len(word) {
		return true
	}

	// Boundary conditions and character mismatch check
	if i < 0 || j < 0 || i >= len(board) || j >= len(board[0]) || board[i][j] != word[k] {
		return false
	}

	// Temporarily mark the cell as visited
	temp := board[i][j]
	board[i][j] = ' '

	// Check all four possible directions (down, up, right, left)
	found := dfs(board, i+1, j, word, k+1) ||
		dfs(board, i-1, j, word, k+1) ||
		dfs(board, i, j+1, word, k+1) ||
		dfs(board, i, j-1, word, k+1)

	// Restore the original character
	board[i][j] = temp

	return found
}

// Main function to check if the word exists in the board
func exist(board [][]byte, word string) bool {
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			// If the first character matches, start the search
			if board[i][j] == word[0] {
				if dfs(board, i, j, word, 0) {
					return true
				}
			}
		}
	}
	return false
}

// Driver function
func main() {
	board := [][]byte{
		{'A', 'B', 'C', 'E'},
		{'S', 'F', 'C', 'S'},
		{'A', 'D', 'E', 'E'},
	}
	word := "ABCCED"

	if exist(board, word) {
		fmt.Println("Word found!")
	} else {
		fmt.Println("Word not found!")
	}
}

Complexity Analysis

Time Complexity : O(N * M * 4^L) where N is rows, M is columns and L is the word length; recursive search through board.

Space Complexity : O(L) due to recursive call stack depth, where L is the length of the word.

1d:T691,class Solution { public: // Helper function to check if the word exists starting from cell (i, j) bool func(vector > & v, int i, int j, string& s, int k) { // If all characters of the word are found if (k == s.length()) { return true; } // Boundary conditions and character mismatch check if (i < 0 || j < 0 || i >= v.size() || j >= v[0].size() || s[k] != v[i][j]) { return false; } // Initialize answer as false bool ans = false; // Temporarily mark the cell as visited char x = v[i][j]; v[i][j] = ' '; // Check all four possible directions (down, up, right, left) ans |= func(v, i + 1, j, s, k + 1); ans |= func(v, i - 1, j, s, k + 1); ans |= func(v, i, j + 1, s, k + 1); ans |= func(v, i, j - 1, s, k + 1); // Restore the original character in the cell v[i][j] = x; return ans; } // Main function to check if the word exists in the board bool exist(vector >& board, string word) { // Iterate through each cell in the board for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[0].size(); j++) { // If the first character matches, start the search if (board[i][j] == word[0]) { // If the word is found, return true if (func(board, i, j, word, 0)) { return true; } } } } // If the word is not found, return false return false; } };1e:T6d0,public class Solution { // Helper function to check if the word exists starting from cell (i, j) private bool SearchWord(char[][] board, int i, int j, string word, int k) { // If all characters of the word are found if (k == word.Length) { return true; } // Boundary c