Problem
Given a n*n matrix containing characters, find if the given word can be found in any direction
For example ,
The output for above problem is true since the word ABCGK can be found in the matrix.
Try out the solution here:
https://leetcode.com/problems/word-search/
Solution:
The solution to this problem is backtracking
You start with a letter in the matrix and then you search if the next letter matches the next letter of the given word.
If it doesn’t you look in the four directions in the matrix : Left , Right, Up and Down.
If any of them match you carry on the same for the remaining letters in the word recursively.
If they don’t match at any stage , you backtrack.
You go back to where you started and start again from the next letter in the matrix.
Keep doing this until you cover the entire matrix or if the word is found.
To keep track of the letters already covered while looking in four directions assign a non ascii character to the covered letters. You can later revert them if you want the matrix to be unchanged.
How to know when word is found?
In the backtracking method you pass the index of the word recursively . If the first index matches then you pass the next index and then the next and so on until you reach the end of the word .After this the index matches the word length and this is when you know the word is found.
How to make sure you don’t track the same letters again?
When you search for the next letter you check up, down , left and right in the matrix .
If any letter matches the next letter in the given word , you again search up,down,left and right.
During this step you might check the same letter again and again.
To prevent this once you track a letter replace it with a non ascii word .
In every backtracking call if the current letter does not match the letter at the given word index then you will return false immediately before doing the above steps.
Here is the algorithm:
ALGORITHM:
STEP 1: For each element in the matrix do backtracking as follows:
STEP 2: Check if index matches the word length , then it means the word is found , return true
STEP 3: Check if row boundaries or column boundaries are exceeded then return false. If the letter at the given index does not match the current element represented by the current row and current column return false as well.
STEP 4: If you land on step 4, then it means the current letter matches the letter at the given index. So to make sure it is not processed again replace it with a “#” or any non ascii character.
STEP 5: Check every element up , down , left and right to see if the next letter in the word matches recursively. The recursive call will make sure that the next to next letter and then the next to next to next letter are matched in all four directions. If true is returned then it means the matching word is found , so return true.
STEP 6: If STEP 5 doesn’t return true , then it means the word is not found so replace the “#” letter again to what was present previously to start over the search again from the next letter in the matrix.
Code:
class Solution {
public boolean exist(char[][] board, String word) {
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(backtrack(board,i,j,word,0)){
return true;
}
}
}
return false;
}
private boolean backtrack(char[][] board,int row,int column,String word,int index){
if(index == word.length()){
return true;
}
if(row < 0 || row == board.length || column <0 || column == board[0].length
|| board[row][column] != word.charAt(index)){
return false;
}
board[row][column] = '#';
int[] rowPos = {-1,0,0,1};
int[] colPos = {0,-1,1,0};
for(int i =0;i<4;i++){
if(backtrack(board,row+rowPos[i],column+colPos[i],word,index+1)){
return true;
}
}
board[row][column] = word.charAt(index);
return false;
}
}
The above code modifies the matrix at the position where the letters are found:
If you don’t want the input matrix to be modified then you can modify the last for loop and the final return statement as below:
boolean result = false;
for(int i =0;i<4;i++){
result = backtrack(board,row+rowPos[i],column+colPos[i],word,index+1);
if(result){
break;
}
}
board[row][column] = word.charAt(index);
return result;
from:
for(int i =0;i<4;i++){
if(backtrack(board,row+rowPos[i],column+colPos[i],word,index+1)){
return true;
}
}
board[row][column] = word.charAt(index);
return false;
}
Time complexity:
Time complexity is O(n * 3 L ) where n is the number of elements in the matrix and L is the number of letters in the word.
O( 3 L ) is the time complexity taken for the backtracking call
Since we make the backtracking call for every element in the matrix time complexity is O(n * 3 L )
Since we look for the next letter in four directions and in each direction we make a recursive call , the backtracking method should ideally have a time complexity of O(4 L ) in the worst case. But after the first two letters are found , subsequent letters will be only searched in three directions recursively because there would be already a letter present in the previous position (replaced by “#”).
So we take the time complexity of the backtracking call to be O(3 L ).
That’s it!
Leave a Reply