Coder's Cat

LeetCode: Word Search

2020-02-11

LeetCode Challenge Description

This is a classic Depth-first-search challenge.

In dfs, we use position parameters i and j to track current postion, depth is the search depth, which could be used to get current character from word.

Time complexity: $O(N^2)$.

#include <queue>
using namespace std;

class Solution {
vector<vector<bool> > visited;
public:
bool dfs(vector<vector<char> >& board, int i, int j, string word, int depth) {
if(board[i][j] != word[depth])
return false;
if(depth >= (word.size() - 1))
return true;
visited[i][j] = true;
int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
for(int k=0; k<4; k++) {
int nx = i + dir[k][0];
int ny = j + dir[k][1];
if(nx >= 0 && nx < board.size() &&
ny >= 0 && ny < board[0].size() && !visited[nx][ny]) {
if(dfs(board, nx, ny, word, depth+1))
return true;
}
}
visited[i][j] = false;
return false;
}

bool exist(vector<vector<char> >& board, string word) {
if(board.size() == 0 || word.length() == 0)
return false;
visited =
vector<vector<bool> >(board.size(), vector<bool>(board[0].size(), false));
for(int i=0; i < board.size(); i++) {
for(int j=0; j < board[0].size(); j++) {
if(dfs(board, i, j, word, 0))
return true;
}
}
return false;
}
};

Preparing for an interview? Check out this!