Problem Statement:
You are given a 2D board(N rows and M columns) of characters and a string “word”. Your task is to check if the given word exists in the grid or not. 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
Constraints:
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15boardandwordconsists of only lowercase and uppercase English letters.
Solution : Using DFS
- Our goal is to find if the given word exists in the matrix or not. We only have to look at the adjacent cells (ignore the diagonal ones).
- One quick look at the problem can suggest that we can solve this by Backtracking. Match character-by-character, go ahead and check if the adjacent cells match the next character, and go back if it does not match.
- The question is How should we traverse the matrix efficiently??
- We need to think of a traversal approach. BFS? DFS? Both can work. But DFS will be better as it immediately checks the next node of the graph and returns if it is not needed after marking it as visited.
Steps:
- Traverse the entire matrix, For each cell (i,j)
- Check if matrix[i][j] == word[index]. (we are using
indexto keep track of the characters that we have already checked in thewordduring backtracking.) - If step 2 is true, then check to repeat the same process for the adjacent cells and for the next index in the word.
- If step 2 is false, then return to the previous state where we received a
truevalue and then further check any remaining and unvisited cells.
Note: We mark each cell as unvisited after we check all the adjacent possibilities because we might visit that cell again when we start traversing the matrix from a different source cell.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
//C++ //Yellow Coding bool exist(vector<vector<char>>& board, string word) { int n=board.size(); if(n==0) return false; int m=board[0].size(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { //DFS for every cell by word[0] if(dfs(i,j,0,board,n,m,word)) return true; } } return false; } //start exploring all the ways, No need to check valid. since base condition will take care of it. bool dfs(int x,int y,int idx,vector<vector<char>>& board,int n,int m,string word) { //if it reaches invalid cell or invalid condition return false if(x<0 or y<0 or x>n-1 or y>m-1 or idx>word.size()-1 or board[x][y]!=word[idx] ) return false; //if you completed the word length succesfully return true if(idx == word.size() - 1) return true; char tmp = board[x][y]; //Without using visited matrix, Replace with unused char in board to indicate visited. board[x][y]='#'; bool isFound = dfs(x,y-1,idx+1,board,n,m,word) || dfs(x+1,y,idx+1,board,n,m,word) || dfs(x,y+1,idx+1,board,n,m,word) || dfs(x-1,y,idx+1,board,n,m,word); // Restore the original char to indicate unvisited for other cells. board[x][y]=tmp; return isFound; } |
Time Complexity: O(M*N*4^L)
L- Length of given word.
For a given start point (i,j), it is impossible for you to search beyond the length of L and for each grid, we have four directions in general. Thus time complexity is O(MN4^L)
Space Complexity: O(L)
- Recursion call stack
Similar Problems:
https://yellowcoding.com/tag/matrix/
https://yellowcoding.com/tag/dfs/
Additionals:
https://en.wikipedia.org/wiki/Word_search
https://www.codingninjas.com/codestudio/problem-details/word-search_892986
https://leetcode.com/problems/word-search/
https://rosettacode.org/wiki/Word_search
