# [leetcode] Word Search

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

```[
["ABCE"],
["SFCS"],
]
```

word = `"ABCCED"`, -> returns `true`,
word = `"SEE"`, -> returns `true`,
word = `"ABCB"`, -> returns `false`.

10/2/2015 update

The previous solution is quite violent. It used a marker ‘\0’ to mark a cell as visited. In this newer solution, I allocate a hashtable to store the visited map.

It is imported to retrieve the spot before return from current node.

```erase first char in word
add current cell to visited hashmap
//do some work, go deeper

insert the erased char to the beginning of word
remove current cell from visited hashmap```
```class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
unordered_map<int, int> visited;
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[0].size(); j++){
if(DFS(board, word, visited, i, j)){
return true;
}
}
}
return false;
}
bool DFS(vector<vector<char> >& board, string& word, unordered_map<int, int>&visited, int r, int c){
//base condition
if(word.size() == 0) return true;

//out of boundary
if(r < 0 || r >= board.size() || c < 0 || c >= board[0].size()){
return false;
}

//visited or not
if(visited.find(r * board[0].size() + c) != visited.end()) return false;

//not match
if(board[r][c] != word[0]) return false;

//board[r][c] == word[0]
word.erase(0, 1);
visited[r * board[0].size() + c] = 1;

int dict[][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
for(int k = 0; k < 4; k++){
int nr = r + dict[k][0];
int nc = c + dict[k][1];
if(DFS(board, word, visited, nr, nc)){
return true;
}
}
visited.erase(r * board[0].size() + c);
word.insert(0, 1, board[r][c]);
return false;
}
};```

```class Solution {
public:
bool exist(vector<vector<char> > &board, string word) {
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[0].size(); j++){
if(_exist(board, word, i, j) == true){
return true;
}
}
}
return false;
}
bool _exist(vector<vector<char>> &board, string word, int r, int c){
if(word.empty()){
return true;
}
if(r < 0 || r >= board.size() || c < 0 || c >= board[0].size()){
return false;
}
if(board[r][c] != word[0]){
return false;
}
else{//board[r][c] == word[0]
char tmp = board[r][c];
board[r][c] = '\0'; //mark as visited, but if a valid result is found, it will
word.erase(0, 1);
for(int i = -1; i <= 1; i += 2){
if(_exist(board, word, r + i, c) == true){
return true;
}
}
for(int j = -1; j <= 1; j += 2){
if(_exist(board, word, r, c + j) == true){
return true;
}
}
board[r][c] = tmp;
return false;
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.