# word search

interview 1
unknown
c_cpp
2 years ago
2.2 kB
0
Indexable
Never
```/*

n*n, n<=6; w<=15

T(n,w) <= n*n*3^(w-1) == 36*3^14 = 60000 * 81 * 36 <= 10^8 * 2

for i :
for j :
int w_i = 0 // next letter in w to be matched
if w[w_i] == grid[i][j] :
bool 2-D array vis : init to false
vis[i][j] = true
dfs(vis, grid, i, j, w_i + 1)

bool dfs(&vis, &grid, i, j, w_i) :
if w_i == w.length :
return true

bool ret = false
check all neighbours (in,jn) of (i,j) :
if w[w_i] == grid[in][jn] && vis[in][jn] == false:
vis[in][jn] = true
ret |= dfs(vis, grid, in, jn, w_i + 1)
vis[in][jn] = false
return ret

*/

class Solution {
public:
int di[4] = {1,0,-1,0};
int dj[4] = {0,1,0,-1}; //down,up,left,right
bool dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, string& word, int par_i, int par_j, int word_counter) {
if (word_counter == word.size()) {
return true;
}

bool found = false;
for (int d = 0; d < 4; d++) {
int i = par_i + di[d];
int j = par_j + dj[d];
if (i >= 0 and i < board.size() and j >=0 and j < board[0].size() and word[word_counter] == board[i][j] and !visited[i][j]) {
visited[i][j] = true;
found |= dfs(board, visited, word, i, j, word_counter + 1);
visited[i][j] = false;
}
}
return found;
}

bool exist(vector<vector<char>>& board, string word) {
int n = board.size();
if (n == 0) {
return word.empty();
}
int m = board[0].size();
if (m == 0) {
return word.empty();
}

int w_i = 0;
vector<vector<bool>> visited(n, vector<bool>(m, false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (word[w_i] == board[i][j]) {
visited[i][j] = true;
if (dfs(board, visited, word, i, j, w_i + 1)) {
return true;
}
visited[i][j] = false;
}
}
}
return false;
}
};```