Difficulty: N/A | Solved: January 1, 0001

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.

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: false

Brain storming

Brute force

On the face of it seems similar to the number of islands problem [[Number of Islands]] where we first try to find 1 “land” in the whole grid and from there we trigger an DFS search for all the land pieces surrounding it , only to stop when we hit “water” we can probably model that here too

start from the top left iterate till you find the first char of the word
If you don’t return false
if you do using a DFS helper you recurse depth first in all directions to find the remaining characters till the time the end of the string is reached
The only catch here is you would have to maintain the order so for eg if the word is “ABC” and you find A then what matters is you find B and then C otherwise its not a valid word

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABC"

def get_words_dfs(row, col, board, char, word):
	# base case to stop DFS
	# search in all directions the next char 

# rows
m = len(board)
# col
n = len(board[0])

start_char = word[0]

for i in range(m):
	for j in range(n):
		if board[i][j] == start_char:
			get_word_dfs(i,j,board)

print(False)

the DFS helper can be like

for the current char if we found it then return with true
if not just break the DFS helper only needs to go 1 step in each direction for the char to hunt , if it does find the char then the dfs helper goes in all valid direction for the next char if however it does not find the char then it just exits and returns false

so the way this problem defers from the standard number of islands is because the dfs helper there explores till it finds the base case which is when it finds 0 but here it might have to come back to the original board after find the char

say in ABCD it finds B in board[2][2] then we recurse to say [1,2], [2,1] [2,3] [3,2] and we find C in [2,1] then we need to continue from there

okay lets scratch that above idea for a moment so it is similar to the standard dfs , the only difference is after we find the current char we recurse in all four directions for the next char ~~so the way this problem defers from the standard number of islands is because the dfs helper there explores till it finds the base case which is when it finds 0 but here it might have to come back to the original board after find the char ~~


def dfs_word_search(row, col,index, board, word):
	# base case , we also need base case for the edge conditions for index and the row and col
	if board[row][col] != word[index]:
		return False
	
	# we now know that we have found the char but we cannot return true yet since the whole word needs to be found
	dfs_word_search(row+1, col, index+1, board)
	dfs_word_search(row-1, col, index+1, board)
	dfs_word_search(row, col+1, index+1, board)
	dfs_word_search(row, col-1, index+1, board)

🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-07 12:17) - (end:: 2025-12-07 12:37)

Optimal Solution

This is an absolutely outstanding start. You’ve spent 20 minutes and have already correctly identified:

The overall strategy: A main loop to find the starting letter, which then triggers a search.
The correct tool for the search: DFS (recursion).
The key difference from Number of Islands: The search is ordered and must follow the sequence of characters in the word.
The state needed for the DFS helper: (row, col) for position, and index to track progress in the word.
The recursive step: From (row, col), explore all four neighbors for the next character at index + 1.

Your dfs_word_search skeleton is almost perfect. You’ve built a strong foundation. Now, let’s refine it with the “self-nudge” questions to make it a complete, working backtracking algorithm.

Question 1: The Base Cases (The “Stop” Conditions)

Your DFS needs to know when to stop. There are two main “stop” conditions.

Success: How do you know you have successfully found the entire word? What would the value of index be? What should the function return in this case?
Failure: You have one failure case (board[row][col] != word[index]), which is good. But what are the other ways a path can fail? Think about the row and col values. What if the search tries to go off the board?

(Prompt): Define the two key base cases: one for success and one for “out of bounds.” What should each return?

Question 2: “Consuming” a Path (The Backtracking “Undo”)

The problem states you cannot use the same letter cell twice.

board = [["A", "B"], ["C", "A"]], word = "ABA"
The path (0,0) -> (0,1) -> (1,1) should be invalid because you can’t reuse the first “A”.

This means when you “use” a character at (row, col) for your current path, you must temporarily mark it as “visited” or “unavailable” so that the recursive calls for the next character don’t accidentally use it again.

After those recursive calls are completely finished exploring, what must you do to that character’s state on the board?

(Prompt): This is a classic “Choose, Explore, Undo” backtracking pattern.

What is the “Choose” step here? (It’s more than just being at a cell).
What is the “Undo” step? How do you restore the board to its original state for other search paths?

Question 3: Reconciling the Recursive Calls

Your recursive step is:

dfs_word_search(row+1, col, index+1, board)
dfs_word_search(row-1, col, index+1, board)
# ... etc.

These calls will return True or False. If the call dfs_word_search(row+1, ...) finds the rest of the word, it will eventually return True. How does the current function know that one of its children succeeded?

(Prompt): How do you combine the boolean results from your four recursive calls? If any one of them returns True, what should the current function do?

2. Base Cases (Excellent, let’s just make them precise)

Success: You said index == len(word) - 1. This is the moment you find the last letter. So, this is the successful end of the path. You’re right! What should you return here? True.
Boundary Case: You said row > len(board) etc. Perfect. A common way to write this check is at the very beginning of the function: if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]): return False. This handles all out-of-bounds cases.
Character Mismatch: You have this: board[row][col] != word[index]. This is also a failure.

So, your base cases are:

Out of bounds? -> False
Character doesn’t match? -> False
Have we found the last letter (index == len(word) - 1)? -> True

This looks good, but can we simplify? What if the word has only one letter, “A”? Your main loop finds ‘A’. It calls dfs(..., index=0). index=0 is len("A")-1. The function would return True immediately, which is correct. What if the word is “AB”? The main loop finds ‘A’, calls dfs(..., index=1). The recursive call for ‘B’ would have index=1, which is len("AB")-1, and would return True. This seems to work.

Let’s consider another way to structure the base case. What if we check for success when index == len(word)? This would mean we have successfully found all characters from index 0 to len(word)-1. It’s a slightly different but very common way to structure it. Let’s stick with your index == len(word) - 1 for now as it’s a valid way to think.

3. “Consuming” a Path (Perfect!)

You said: we can "sink" the word and then continue our recursive calls and then once done we can "unsink" it ie remark it?

This is exactly what backtracking is. It is the perfect “Choose, Explore, Undo” pattern.

“Sink” (Choose): Before you make the recursive calls for the neighbors, you need to change board[row][col] to a special character (like # or None) to mark it as “currently in use on this path.”
“Explore”: Make your four recursive calls.
“Unsink” (Undo): After the recursive calls are all done (regardless of whether they succeeded or failed), you must restore the board: board[row][col] = original_char. This is the crucial cleanup step that allows other search paths to use this character.

You have all the pieces.

(Prompt): Now, assemble these corrected pieces into a single dfs_word_search function. Pay close attention to the order of operations.

Handle the failure base cases first (out of bounds, character mismatch).
Handle the success base case.
Implement the “Sink, Explore, Unsink” logic.
Use the correct boolean operator (or) to combine the results of the “Explore” step.


def dfs_word_search(row, col, index, word, board):
	# failed base case 1 for boundary cases 
	if row < 0 or row >= len(board) or col < 0 or col > len(board[0]): 
		return False
	# failed base case 2 for character mismatch
	if board[row][col] != word[index]:
		return False
	# pass base case for finding all the characters
	if index == len(word)-1:
		return True
	
	# choose 
	original_char = board[row][col]
	board[row][col] = '#' # sink character
	
	# Explore
	left = dfs_word_search(row-1, col, index+1, word, board)
	right = dfs_word_search(row+1, col, index+1, word, board)
	top = dfs_word_search(row, col-1, index+1, word, board)
	bottom = dfs_word_search(row, col+1, index+1, word, board)
	
	# undo
	board[row][col] = original_char
	
	return left or right or top or bottom

YES! That’s it. It’s perfect.

You’ve corrected the index + 1 in the recursive calls, which was the final logical piece. Your code is now a complete, correct, and robust solution for the DFS part of the Word Search problem.

Let’s do a final review of the powerful patterns you’ve implemented:

Guard Clauses (Base Cases): Your if statements at the top cleanly handle all the “failure” conditions (out of bounds, character mismatch) right away. This makes the rest of the code cleaner.
Success Base Case: Your if index == len(word) - 1: correctly identifies when the last character has been found, stopping the recursion and returning True.
“Choose” (State Modification): board[row][col] = '#' is the perfect “Choose” step. You are temporarily modifying the shared state (the board) to reflect the path you are currently on.
“Explore” (Recursion): Your four recursive calls correctly explore all possibilities from the current state, passing the updated state (index + 1) to the next level.
“Undo” (State Restoration): board[row][col] = original_char is the crucial “Undo” step. It ensures that after this path is fully explored, the board is clean for other starting points or sibling paths in the recursion. This is the essence of backtracking.
Result Aggregation: return left or right or top or bottom correctly propagates a True signal up the call stack as soon as any path finds the solution.

Final version

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABC"


def dfs_word_search(row, col, index, word, board):
	# failed base case 1 for boundary cases 
	if row < 0 or row >= len(board) or col < 0 or col > len(board[0]): 
		return False
	# failed base case 2 for character mismatch
	if board[row][col] != word[index]:
		return False
	# pass base case for finding all the characters
	if index == len(word)-1:
		return True
	
	# choose 
	original_char = board[row][col]
	board[row][col] = '#' # sink character
	
	# Explore
	left = dfs_word_search(row-1, col, index+1, word, board)
	right = dfs_word_search(row+1, col, index+1, word, board)
	top = dfs_word_search(row, col-1, index+1, word, board)
	bottom = dfs_word_search(row, col+1, index+1, word, board)
	
	# undo
	board[row][col] = original_char # unsink the character
	
	return left or right or top or bottom


def word_search(board, word):
	m = len(board) # rows
	n = len(board[0]) # columns	
	start_char = word[0] # start char
	start_index = 1 # start index (this is incorrect because the search should start from the character index that is just found)
	for i in range(m):
		for j in range(n):
			if board[i][j] == start_char: # find the start char
				# start dfs + back tracking
				if dfs_word_search(i,j,0,word,board):
				# If and ONLY IF this specific search was a success... # ...then we can stop everything and report success.
					return True
	
	return False
		

print(word_search(board, word))

This is a common logical step that’s easy to miss.

Right now, your code says: “Find the first character. If you find it, start a search. Whatever that search returns (True or False), immediately stop and return that result.”

What you want it to say is: “Find the first character. If you find it, start a search. If that search is successful (returns True), then we are done and can return True. If it’s not successful, then just keep looking for other possible starting characters in the grid.”

The fix is very simple. You just need to wrap your call to the DFS helper in its own if statement.

Previous Code:

if board[i][j] == start_char:
    # This search_result will be either True or False
    search_result = dfs_word_search(i, j, 0, word, board)
    # You are immediately returning whatever it is.
    return search_result

Current Corrected Logic:

if board[i][j] == start_char:
    # Start a search.
    if dfs_word_search(i, j, 0, word, board) == True:
        # If and ONLY IF this specific search was a success...
        # ...then we can stop everything and report success.
        return True
# If the loops finish without any of the DFS calls returning True,
# it means the word was never found.
return False

Let’s trace this corrected logic with our word = "ASAD" example.

Loop finds ‘A’ at (0,0).
if dfs(0,0,0, ...) is called.
Let’s assume this path fails, so the dfs call returns False.
The inner if False == True: condition is not met.
The for loops continue. They don’t stop.
Eventually, the loops get to i=1, j=0. board[1][0] is ‘A’.
if dfs(1,0,0, ...) is called.
Let’s assume this path succeeds ((1,0) -> (0,1) -> (0,0) -> (1,1) is not a valid path, but assume (1,0)->(0,0)->(0,1)->... finds the word). The dfs call returns True.
The inner if True == True: condition is met.
The main function return True and everything stops.

This structure ensures you only exit the function early on a success, allowing the search to continue from all possible starting points if the initial ones are dead ends.

(Prompt): Can you integrate this corrected if block into your final word_search function?

🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-07 12:38) - (end:: 2025-12-07 13:09)