79. Word Search#
Difficulty: Medium
Link to Problem: To see the Word Search problem on LeetCode, click here!
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.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board
andword
consists of only lowercase and uppercase English letters.
Follow up: Could you use search pruning to make your solution faster with a larger board
?
Probelm Explanation:#
The problem is to determine whether a given word can be constructed from characters in an m x n
grid of characters. The word can be formed by moving sequentially through horizontally or vertically neighboring cells in the grid, and you cannot use the same cell more than once.
Here are the specifics of the problem:
You are given an
m x n
grid, which is a 2D board of characters.You are also given a string
word
consisting of lowercase and uppercase English letters.Your task is to determine if the word can be found in the grid by moving from one cell to an adjacent cell (horizontally or vertically) and collecting the characters sequentially to form the word.
You can’t use the same cell more than once when forming the word.
If it’s possible to form the word in the grid, return
True
; otherwise, returnFalse
.
For example, consider the following grid and word:
board = [["A", "B", "C", "E"],
["S", "F", "C", "S"],
["A", "D", "E", "E"]]
word = "ABCCED"
In this case, the word “ABCCED” can be formed by moving through the cells (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,3) in the grid. Therefore, the function should return True
.
Conversely, if the word is impossible to construct, such as in the case of the word “ABCB” for the same grid, where there’s no valid path that forms the word, the function should return False
.
The problem involves searching for a path through the grid that matches the characters in the word while respecting the constraints mentioned. It can be solved using depth-first search (DFS) or backtracking.
Solution:#
Here’s a Python function to implement this algorithm:
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k):
# Check if the current position is out of bounds or doesn't match the character in the word.
if not (0 <= i < len(board)) or not (0 <= j < len(board[0])) or board[i][j] != word[k]:
return False
# If we have matched all characters in the word, return True.
if k == len(word) - 1:
return True
# Temporarily mark the current cell to prevent revisiting.
tmp, board[i][j] = board[i][j], "/"
# Explore adjacent cells by making recursive calls in all four directions.
found = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
# Restore the original character in the cell.
board[i][j] = tmp
return found
# Iterate through all cells in the board.
for i in range(len(board)):
for j in range(len(board[0])):
# Check if the 'dfs' function starting from this cell returns True.
if dfs(i, j, 0):
return True
# If no match is found after exploring all cells, return False.
return False
Explanation:#
Import the necessary module:
from typing import List
: This line imports theList
type from thetyping
module, which is used to specify the type of theboard
parameter in the method signature.
Define the
Solution
class:class Solution:
: This line defines a class calledSolution
to encapsulate the solution for the word search problem.
Define the
exist
method:def exist(self, board: List[List[str]], word: str) -> bool:
: This method is a member of theSolution
class and takes two parameters:board
, which is a 2D list of characters, andword
, which is a string. It returns a boolean value, indicating whether the word exists in the board.
Implement the inner
dfs
function:def dfs(i, j, k):
: This is a helper function used for depth-first search (DFS). It is called recursively to explore the board and search for the word. It takes three parameters:i
andj
representing the current position on the board, andk
representing the current index in theword
string.Inside
dfs
, it checks if the current position is out of bounds or if the character at the current position on the board does not match the character at the current index in theword
. If either of these conditions is met, it returnsFalse
.If
k
is equal to the length of theword
minus one, it means we have successfully matched all characters in theword
, so it returnsTrue
.The function then temporarily replaces the character at the current position with a marker, “/”, to prevent revisiting the same cell. It then explores adjacent cells by making recursive calls in all four directions: up, down, left, and right. If any of these recursive calls return
True
, it propagates theTrue
result up the call stack. After the exploration is complete, it restores the original character in the cell.
Iterate through the board:
The outer loop iterates through all cells in the
board
using two nested loops. For each cell, it checks if thedfs
function starting from that cell (withk
initially set to 0) returnsTrue
. If it does, it means the word exists, so the method returnsTrue
.
Return
False
:If the loop completes without finding the word in the board, the method returns
False
.
To use this code, you can create an instance of the Solution
class and call the exist
method on that instance, passing the board
and the word
as arguments to check if the word exists in the board.
Test cases:#
Here’s how you can use this solution:
# Example 1:
# Create an instance of the Solution class
solution = Solution()
# Test case 1: Word "ABCCED" can be found in the grid
board1 = [["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]]
word1 = "ABCCED"
print(solution.exist(board1, word1)) # Expected output: True
True
# Example 2
# Test case 2: Word "SEE" can be found in the grid
word2 = "SEE"
print(solution.exist(board1, word2)) # Expected output: True
True
# Example 3
# Test case 3: Word "ABCB" cannot be found in the grid
word3 = "ABCB"
print(solution.exist(board1, word3)) # Expected output: False
False
Time and Space Complexity Analysis#
Let’s analyze the time and space complexity of the exist
method in the given code.
Time Complexity:
The primary work in this code is done by the dfs
function, which performs a depth-first search through the grid. The time complexity of the dfs
function is \(O(4^(n))\), where “n” is the length of the word
. This is because, in the worst case, the function explores all possible directions (up, down, left, right) for each character in the word
.
The outer loops iterate through all cells in the board
, which has dimensions m x n
. So, the total number of iterations of dfs
is O(m * n). However, since the dfs
function has a higher time complexity, the overall time complexity is still dominated by the dfs
function.
Therefore, the overall time complexity of the exist
method is \(O(m * n * 4^n)\), where “m” and “n” are the dimensions of the board, and “n” is the length of the word.
Space Complexity:
The primary space usage comes from the recursive calls in the
dfs
function. The depth of the recursion can be at most equal to the length of theword
, which is O(n).Additionally, the
tmp
variable and the recursive calls on the call stack consume a small amount of additional memory.The marking of visited cells with the “/” character temporarily modifies the
board
in-place but doesn’t significantly contribute to the space complexity.
Therefore, the overall space complexity is O(n) due to the recursive call stack.
In summary, the time complexity is \(O(m * n * 4^n)\), and the space complexity is O(n), where “m” and “n” are the dimensions of the board, and “n” is the length of the word. The time complexity is exponential in the worst case due to the depth-first search through all possible paths in the grid.
Challenging Exercises:#
Optimization Challenge: Modify the code to find all unique words that can be constructed from the grid. Instead of returning
True
orFalse
, return a list of words found. Ensure that the same cell is not used more than once in constructing each word.Board Generation: Create a function to generate random grids of characters and then use the
exist
method to solve them. Test the efficiency and correctness of your code by generating larger boards and words.