Problem Statement: Word Search
Given an m x n board of characters and a string word, write a function to check if the word exists in the board. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example
Example 1:
- Input:plaintextCopy code
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED" - Output:
trueExplanation: The word"ABCCED"can be constructed from the board by starting atboard[0][0], then moving right toboard[0][1], down toboard[1][1], down toboard[2][1], and right toboard[2][2].
Example 2:
- Input:plaintextCopy code
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "SEE" - Output:
trueExplanation: The word"SEE"can be constructed from the board by starting atboard[2][0], then moving right toboard[2][1], and up toboard[1][1].
Example 3:
- Input:plaintextCopy code
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCB" - Output:
falseExplanation: The word"ABCB"does not exist on the board, because the letter ‘B’ atboard[0][1]is used twice, and we cannot use the same cell twice.
Approach
We can solve this problem using Depth First Search (DFS) to explore possible paths for the word. The idea is to start from each cell and check whether the word can be formed by exploring adjacent cells recursively.
Steps:
- DFS Search: For each character in the board, we will start a DFS search if it matches the first character of the word.
- If the current character matches the corresponding character in the word, recursively search for the next character in the adjacent cells (up, down, left, right).
- If all characters in the word are matched, return
true.
- Backtracking: Since each cell can be used only once, mark the current cell as visited during the DFS search and unmark it once the search is complete for that path (backtrack).
- Boundary Check: Ensure that we don’t go out of bounds when searching adjacent cells.
Time and Space Complexity
- Time Complexity: The time complexity is O(m * n * 4^L), where
mis the number of rows,nis the number of columns, andLis the length of the word. This is because, in the worst case, we explore every possible cell and recursively check all adjacent cells. - Space Complexity: The space complexity is O(m * n) due to the recursion stack (in the worst case, the recursion depth can be the number of cells in the board).
Code Implementations
1. C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || word.empty()) return false;
int m = board.size(), n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (dfs(board, word, i, j, 0, visited)) return true;
}
}
return false;
}
private:
bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index, vector<vector<bool>>& visited) {
if (index == word.size()) return true; // All characters are found
if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || visited[i][j] || board[i][j] != word[index]) {
return false;
}
visited[i][j] = true; // Mark as visited
// Explore in all four directions
bool result = dfs(board, word, i + 1, j, index + 1, visited) ||
dfs(board, word, i - 1, j, index + 1, visited) ||
dfs(board, word, i, j + 1, index + 1, visited) ||
dfs(board, word, i, j - 1, index + 1, visited);
visited[i][j] = false; // Unmark for backtracking
return result;
}
};
int main() {
Solution sol;
vector<vector<char>> board = {
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}
};
string word = "ABCCED";
cout << boolalpha << sol.exist(board, word) << endl; // Output: true
return 0;
}
2. Java
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || word == null || word.length() == 0) return false;
int m = board.length, n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, word, i, j, 0, visited)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
if (index == word.length()) return true; // All characters found
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length ||
visited[i][j] || board[i][j] != word.charAt(index)) {
return false;
}
visited[i][j] = true; // Mark as visited
// Explore four directions
boolean result = dfs(board, word, i + 1, j, index + 1, visited) ||
dfs(board, word, i - 1, j, index + 1, visited) ||
dfs(board, word, i, j + 1, index + 1, visited) ||
dfs(board, word, i, j - 1, index + 1, visited);
visited[i][j] = false; // Unmark for backtracking
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
char[][] board = {
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}
};
String word = "ABCCED";
System.out.println(sol.exist(board, word)); // Output: true
}
}
3. Python
class Solution:
def exist(self, board, word):
if not board or not word:
return False
m, n = len(board), len(board[0])
visited = [[False] * n for _ in range(m)]
def dfs(i, j, index):
if index == len(word):
return True
if i < 0 or j < 0 or i >= m or j >= n or visited[i][j] or board[i][j] != word[index]:
return False
visited[i][j] = True # Mark as visited
# Explore all four directions
result = (dfs(i + 1, j, index + 1) or
dfs(i - 1, j, index + 1) or
dfs(i, j + 1, index + 1) or
dfs(i, j - 1, index + 1))
visited[i][j] = False # Unmark for backtracking
return result
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
# Example usage
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED"
sol = Solution()
print(sol.exist(board, word)) # Output: True
4. C#
public class Solution {
public bool Exist(char[][] board, string word) {
if (board == null || board.Length == 0 || word == null || word.Length == 0) return false;
int m = board.Length, n = board[0].Length;
bool[,] visited = new bool[m, n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (DFS(board, word, i, j, 0, visited)) return true;
}
}
return false;
}
private bool DFS(char[][] board, string word, int i, int j, int index, bool[,] visited) {
if (index == word.Length) return true; // All characters found
if (i < 0 || j < 0 || i >= board.Length || j >= board[0].Length ||
visited[i, j] || board[i][j] != word[index]) {
return false;
}
visited[i, j] = true; // Mark as visited
// Explore all four directions
bool result = DFS(board, word, i + 1, j, index + 1, visited) ||
DFS(board, word, i - 1, j, index + 1, visited) ||
DFS(board, word, i, j + 1, index + 1, visited) ||
DFS(board, word, i, j - 1, index + 1, visited);
visited[i, j] = false; // Unmark for backtracking
return result;
}
}
class Program {
static void Main() {
var board = new char[][] {
new char[] {'A','B','C','E'},
new char[] {'S','F','C','S'},
new char[] {'A','D','E','E'}
};
string word = "ABCCED";
var sol = new Solution();
Console.WriteLine(sol.Exist(board, word)); // Output: True
}
}
5. JavaScript
var exist = function(board, word) {
if (!board || !word) return false;
const m = board.length, n = board[0].length;
const visited = Array.from({ length: m }, () => Array(n).fill(false));
function dfs(i, j, index) {
if (index === word.length) return true;
if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] !== word[index]) {
return false;
}
visited[i][j] = true; // Mark as visited
// Explore four directions
const result = dfs(i + 1, j, index + 1) ||
dfs(i - 1, j, index + 1) ||
dfs(i, j + 1, index + 1) ||
dfs(i, j - 1, index + 1);
visited[i][j] = false; // Unmark for backtracking
return result;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
};
// Example usage
const board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
];
const word = "ABCCED";
console.log(exist(board, word)); // Output: true
6.C
#include <stdio.h>
#include <stdbool.h>
#define MAX_ROWS 100
#define MAX_COLS 100
// Directions: Up, Down, Left, Right
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool dfs(char board[MAX_ROWS][MAX_COLS], int m, int n, const char* word, int wordIndex, int i, int j, bool visited[MAX_ROWS][MAX_COLS]) {
// Base condition: if we've matched the entire word
if (word[wordIndex] == '\0') {
return true;
}
// If out of bounds or current cell doesn't match the word character or already visited, return false
if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[wordIndex]) {
return false;
}
// Mark the current cell as visited
visited[i][j] = true;
// Explore all 4 possible directions (Up, Down, Left, Right)
for (int d = 0; d < 4; d++) {
int newRow = i + directions[d][0];
int newCol = j + directions[d][1];
// Recursively search the next character in the word
if (dfs(board, m, n, word, wordIndex + 1, newRow, newCol, visited)) {
return true;
}
}
// Unmark the current cell as visited for backtracking
visited[i][j] = false;
return false;
}
bool exist(char board[MAX_ROWS][MAX_COLS], int m, int n, const char* word) {
if (!board || !word) return false;
// Create a visited array to mark cells we've already visited
bool visited[MAX_ROWS][MAX_COLS] = {{false}};
// Try to find the word starting from every cell in the board
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Start DFS search if the first character matches
if (board[i][j] == word[0] && dfs(board, m, n, word, 0, i, j, visited)) {
return true;
}
}
}
return false;
}
int main() {
char board[MAX_ROWS][MAX_COLS] = {
{'A', 'B', 'C', 'E'},
{'S', 'F', 'C', 'S'},
{'A', 'D', 'E', 'E'}
};
int m = 3, n = 4;
const char* word = "ABCCED";
if (exist(board, m, n, word)) {
printf("Word found\n");
} else {
printf("Word not found\n");
}
return 0;
}Conclusion
The Word Search problem is a typical backtracking problem that can be solved efficiently using DFS with backtracking. By marking cells as visited during the search and backtracking when necessary, we can explore all possible paths for the word in the grid.