Language Selection
Choose your preferred programming language
Showing: Python
Word Search
Problem Statement
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.
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 61 <= word.length <= 15boardandwordconsist of only lowercase and uppercase English letters
Examples:
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation: The path is A(0,0) -> B(0,1) -> C(0,2) -> C(1,2) -> E(2,2) -> D(2,1)
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation: The path is S(1,3) -> E(2,3) -> E(2,2)
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Explanation: No valid path exists because B(0,1) would need to be reused.
Approach 1: DFS Backtracking
Algorithm:
- Iterate through every cell in the grid as a potential starting point
- From each starting cell, perform DFS exploring all four directions (up, down, left, right)
- Mark cells as visited by temporarily modifying them (e.g., replacing with
#) - If the current cell matches the current character in the word, recurse for the next character
- Backtrack by restoring the original character after exploring all directions
- Return true as soon as the entire word is matched
Time Complexity: O(m * n * 3^L) where L is the word length. For each cell we start DFS, and at each step we branch into at most 3 directions (excluding the cell we came from). Space Complexity: O(L) for the recursion stack depth.
Python:
def exist(board, word):
"""
Search for word in grid using DFS backtracking
Time: O(m * n * 3^L)
Space: O(L) recursion depth
"""
rows, cols = len(board), len(board[0])
def dfs(r, c, index):
if index == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[index]):
return False
# Mark as visited by replacing with a sentinel
temp = board[r][c]
board[r][c] = '#'
# Explore all four directions
found = (dfs(r + 1, c, index + 1) or
dfs(r - 1, c, index + 1) or
dfs(r, c + 1, index + 1) or
dfs(r, c - 1, index + 1))
# Backtrack: restore the original character
board[r][c] = temp
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
Java:
class Solution {
/**
* Search for word in grid using DFS backtracking
* Time: O(m * n * 3^L)
* Space: O(L) recursion depth
*/
public boolean exist(char[][] board, String word) {
int rows = board.length;
int cols = board[0].length;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (dfs(board, word, r, c, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int index) {
if (index == word.length()) {
return true;
}
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length ||
board[r][c] != word.charAt(index)) {
return false;
}
// Mark as visited
char temp = board[r][c];
board[r][c] = '#';
// Explore all four directions
boolean found = dfs(board, word, r + 1, c, index + 1) ||
dfs(board, word, r - 1, c, index + 1) ||
dfs(board, word, r, c + 1, index + 1) ||
dfs(board, word, r, c - 1, index + 1);
// Backtrack: restore the original character
board[r][c] = temp;
return found;
}
}
Go:
// exist - Search for word in grid using DFS backtracking
// Time: O(m * n * 3^L)
// Space: O(L) recursion depth
func exist(board [][]byte, word string) bool {
rows := len(board)
cols := len(board[0])
var dfs func(r, c, index int) bool
dfs = func(r, c, index int) bool {
if index == len(word) {
return true
}
if r < 0 || r >= rows || c < 0 || c >= cols ||
board[r][c] != word[index] {
return false
}
// Mark as visited
temp := board[r][c]
board[r][c] = '#'
// Explore all four directions
found := dfs(r+1, c, index+1) ||
dfs(r-1, c, index+1) ||
dfs(r, c+1, index+1) ||
dfs(r, c-1, index+1)
// Backtrack: restore the original character
board[r][c] = temp
return found
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if dfs(r, c, 0) {
return true
}
}
}
return false
}
JavaScript:
/**
* Search for word in grid using DFS backtracking
* Time: O(m * n * 3^L)
* Space: O(L) recursion depth
*/
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
function dfs(r, c, index) {
if (index === word.length) {
return true;
}
if (r < 0 || r >= rows || c < 0 || c >= cols ||
board[r][c] !== word[index]) {
return false;
}
// Mark as visited
const temp = board[r][c];
board[r][c] = '#';
// Explore all four directions
const found = dfs(r + 1, c, index + 1) ||
dfs(r - 1, c, index + 1) ||
dfs(r, c + 1, index + 1) ||
dfs(r, c - 1, index + 1);
// Backtrack: restore the original character
board[r][c] = temp;
return found;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) {
return true;
}
}
}
return false;
}
C#:
public class Solution {
/// <summary>
/// Search for word in grid using DFS backtracking
/// Time: O(m * n * 3^L)
/// Space: O(L) recursion depth
/// </summary>
public bool Exist(char[][] board, string word) {
int rows = board.Length;
int cols = board[0].Length;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (Dfs(board, word, r, c, 0)) {
return true;
}
}
}
return false;
}
private bool Dfs(char[][] board, string word, int r, int c, int index) {
if (index == word.Length) {
return true;
}
if (r < 0 || r >= board.Length || c < 0 || c >= board[0].Length ||
board[r][c] != word[index]) {
return false;
}
// Mark as visited
char temp = board[r][c];
board[r][c] = '#';
// Explore all four directions
bool found = Dfs(board, word, r + 1, c, index + 1) ||
Dfs(board, word, r - 1, c, index + 1) ||
Dfs(board, word, r, c + 1, index + 1) ||
Dfs(board, word, r, c - 1, index + 1);
// Backtrack: restore the original character
board[r][c] = temp;
return found;
}
}
Approach 2: DFS Backtracking with Optimizations
Algorithm:
- Before searching, count character frequencies in the board and the word. If any character in the word is not present in sufficient quantity on the board, return false immediately.
- If the last character of the word is rarer on the board than the first character, reverse the word to start the search from the rarer end. This reduces the number of starting cells and prunes more branches early.
- Use the same DFS backtracking as Approach 1.
Time Complexity: O(m * n * 3^L) worst case, but significantly faster in practice Space Complexity: O(L) for the recursion stack depth
Python:
from collections import Counter
def exist(board, word):
"""
Search for word in grid with frequency-based optimizations
Time: O(m * n * 3^L) worst case
Space: O(L) recursion depth
"""
rows, cols = len(board), len(board[0])
# Count characters on the board
board_count = Counter()
for r in range(rows):
for c in range(cols):
board_count[board[r][c]] += 1
# Check if the board has enough of each character
word_count = Counter(word)
for ch, count in word_count.items():
if board_count[ch] < count:
return False
# Reverse word if the last character is rarer (optimization)
if board_count[word[0]] > board_count[word[-1]]:
word = word[::-1]
def dfs(r, c, index):
if index == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[index]):
return False
temp = board[r][c]
board[r][c] = '#'
found = (dfs(r + 1, c, index + 1) or
dfs(r - 1, c, index + 1) or
dfs(r, c + 1, index + 1) or
dfs(r, c - 1, index + 1))
board[r][c] = temp
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
Java:
class Solution {
/**
* Search for word in grid with frequency-based optimizations
* Time: O(m * n * 3^L) worst case
* Space: O(L) recursion depth
*/
public boolean exist(char[][] board, String word) {
int rows = board.length;
int cols = board[0].length;
// Count characters on the board
int[] boardCount = new int[128];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
boardCount[board[r][c]]++;
}
}
// Check if the board has enough of each character
int[] wordCount = new int[128];
for (char ch : word.toCharArray()) {
wordCount[ch]++;
if (wordCount[ch] > boardCount[ch]) {
return false;
}
}
// Reverse word if the last character is rarer
if (boardCount[word.charAt(0)] > boardCount[word.charAt(word.length() - 1)]) {
word = new StringBuilder(word).reverse().toString();
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (dfs(board, word, r, c, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int index) {
if (index == word.length()) {
return true;
}
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length ||
board[r][c] != word.charAt(index)) {
return false;
}
char temp = board[r][c];
board[r][c] = '#';
boolean found = dfs(board, word, r + 1, c, index + 1) ||
dfs(board, word, r - 1, c, index + 1) ||
dfs(board, word, r, c + 1, index + 1) ||
dfs(board, word, r, c - 1, index + 1);
board[r][c] = temp;
return found;
}
}
Go:
// exist - Search for word in grid with frequency-based optimizations
// Time: O(m * n * 3^L) worst case
// Space: O(L) recursion depth
func exist(board [][]byte, word string) bool {
rows := len(board)
cols := len(board[0])
// Count characters on the board
boardCount := make(map[byte]int)
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
boardCount[board[r][c]]++
}
}
// Check if the board has enough of each character
wordCount := make(map[byte]int)
for i := 0; i < len(word); i++ {
wordCount[word[i]]++
if wordCount[word[i]] > boardCount[word[i]] {
return false
}
}
// Reverse word if the last character is rarer
searchWord := word
if boardCount[word[0]] > boardCount[word[len(word)-1]] {
runes := []byte(word)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
searchWord = string(runes)
}
var dfs func(r, c, index int) bool
dfs = func(r, c, index int) bool {
if index == len(searchWord) {
return true
}
if r < 0 || r >= rows || c < 0 || c >= cols ||
board[r][c] != searchWord[index] {
return false
}
temp := board[r][c]
board[r][c] = '#'
found := dfs(r+1, c, index+1) ||
dfs(r-1, c, index+1) ||
dfs(r, c+1, index+1) ||
dfs(r, c-1, index+1)
board[r][c] = temp
return found
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if dfs(r, c, 0) {
return true
}
}
}
return false
}
JavaScript:
/**
* Search for word in grid with frequency-based optimizations
* Time: O(m * n * 3^L) worst case
* Space: O(L) recursion depth
*/
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
// Count characters on the board
const boardCount = {};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
boardCount[board[r][c]] = (boardCount[board[r][c]] || 0) + 1;
}
}
// Check if the board has enough of each character
const wordCount = {};
for (const ch of word) {
wordCount[ch] = (wordCount[ch] || 0) + 1;
if (wordCount[ch] > (boardCount[ch] || 0)) {
return false;
}
}
// Reverse word if the last character is rarer
let searchWord = word;
if ((boardCount[word[0]] || 0) > (boardCount[word[word.length - 1]] || 0)) {
searchWord = word.split('').reverse().join('');
}
function dfs(r, c, index) {
if (index === searchWord.length) {
return true;
}
if (r < 0 || r >= rows || c < 0 || c >= cols ||
board[r][c] !== searchWord[index]) {
return false;
}
const temp = board[r][c];
board[r][c] = '#';
const found = dfs(r + 1, c, index + 1) ||
dfs(r - 1, c, index + 1) ||
dfs(r, c + 1, index + 1) ||
dfs(r, c - 1, index + 1);
board[r][c] = temp;
return found;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) {
return true;
}
}
}
return false;
}
C#:
public class Solution {
/// <summary>
/// Search for word in grid with frequency-based optimizations
/// Time: O(m * n * 3^L) worst case
/// Space: O(L) recursion depth
/// </summary>
public bool Exist(char[][] board, string word) {
int rows = board.Length;
int cols = board[0].Length;
// Count characters on the board
Dictionary<char, int> boardCount = new Dictionary<char, int>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (!boardCount.ContainsKey(board[r][c]))
boardCount[board[r][c]] = 0;
boardCount[board[r][c]]++;
}
}
// Check if the board has enough of each character
Dictionary<char, int> wordCount = new Dictionary<char, int>();
foreach (char ch in word) {
if (!wordCount.ContainsKey(ch))
wordCount[ch] = 0;
wordCount[ch]++;
int available = boardCount.ContainsKey(ch) ? boardCount[ch] : 0;
if (wordCount[ch] > available) {
return false;
}
}
// Reverse word if the last character is rarer
string searchWord = word;
int firstCount = boardCount.ContainsKey(word[0]) ? boardCount[word[0]] : 0;
int lastCount = boardCount.ContainsKey(word[^1]) ? boardCount[word[^1]] : 0;
if (firstCount > lastCount) {
char[] arr = word.ToCharArray();
Array.Reverse(arr);
searchWord = new string(arr);
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (Dfs(board, searchWord, r, c, 0)) {
return true;
}
}
}
return false;
}
private bool Dfs(char[][] board, string word, int r, int c, int index) {
if (index == word.Length) {
return true;
}
if (r < 0 || r >= board.Length || c < 0 || c >= board[0].Length ||
board[r][c] != word[index]) {
return false;
}
char temp = board[r][c];
board[r][c] = '#';
bool found = Dfs(board, word, r + 1, c, index + 1) ||
Dfs(board, word, r - 1, c, index + 1) ||
Dfs(board, word, r, c + 1, index + 1) ||
Dfs(board, word, r, c - 1, index + 1);
board[r][c] = temp;
return found;
}
}
Key Insights
In-Place Visited Marking: Instead of maintaining a separate visited matrix, temporarily replace the cell’s character with a sentinel value (e.g.,
#). This saves O(m*n) space and is restored during backtracking.3^L Not 4^L: Although there are 4 directions, we never go back to the cell we just came from (it is marked visited), so the effective branching factor is 3, giving O(3^L) per starting cell.
Early Termination: The DFS returns as soon as a match is found. Short-circuit evaluation (using
||) ensures that once one direction succeeds, the remaining directions are not explored.Character Frequency Check: A pre-check that the board contains enough of each character in the word can immediately return false and avoid expensive DFS entirely.
Reverse Search Optimization: Starting the search from the rarer end of the word reduces the number of valid starting cells and prunes the search tree earlier.
Edge Cases
- Single cell board matching single character word:
board = [["A"]], word = "A"returnstrue - Single cell board not matching:
board = [["A"]], word = "B"returnsfalse - Word longer than total cells: impossible to form, should return
false - All cells have the same character:
board = [["A","A"],["A","A"]], word = "AAAA"requires careful visited tracking - Word requires visiting every cell: tests that backtracking correctly restores state
Test Cases
# Test case 1: Word exists
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
assert exist(board, "ABCCED") == True
# Test case 2: Word exists (different path)
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
assert exist(board, "SEE") == True
# Test case 3: Word does not exist (would require reuse)
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
assert exist(board, "ABCB") == False
# Test case 4: Single cell
assert exist([["A"]], "A") == True
# Test case 5: Word not on board at all
board = [["A","B"],["C","D"]]
assert exist(board, "E") == False
Common Mistakes
- Not restoring the cell after backtracking: Forgetting to set
board[r][c] = tempcauses cells to remain marked as visited, making valid paths unreachable in subsequent searches. - Using a separate visited matrix unnecessarily: While correct, it uses O(m*n) extra space. The in-place sentinel approach is more space-efficient and idiomatic for this problem.
- Checking bounds after accessing the cell: Accessing
board[r][c]before verifying thatrandcare within bounds causes index-out-of-range errors. - Forgetting to try all starting positions: The word can start from any cell, not just the top-left corner. The outer loop over all cells is essential.
- Not short-circuiting on success: Continuing to search after finding the word wastes time. Return
trueimmediately when the word is found.