Last active
April 19, 2020 04:32
-
-
Save sedmo/127b5f296c626a0f5b31c91df42d0732 to your computer and use it in GitHub Desktop.
find word in grid of characters. return true if the word exists
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
private: | |
bool dfs(vector<vector<char>>&board, int count, int i, int j, string& word) | |
{ | |
if(word.size() == count) //Signifies that we have reached the end of search | |
return true; | |
if(i<0 || j<0 || i>=board.size() || j>=board[0].size() || board[i][j]!=word[count]) | |
return false; | |
//We check if element is within bounds and then check if the character at that is the same as the corresponding character in string word | |
char temp = board[i][j]; | |
board[i][j] = ' '; //To show that we have visited this node | |
bool res = dfs(board, count+1, i+1, j, word) || dfs(board, count+1, i-1, j, word) || dfs(board, count+1, i, j+1, word) ||dfs(board, count+1, i, j-1, word); //DFS in all 4 directions | |
board[i][j] = temp; //Restore the element after checking | |
return res; | |
} | |
public: | |
bool exist(vector<vector<char>>& board, string word) { | |
if(board.empty()) return false; | |
for(int i = 0; i < board.size(); i++){ | |
for(int j = 0; j < board[i].size(); j++){ | |
if(dfs(board, 0, i, j, word)) | |
return true; | |
} | |
} | |
return false; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment