Description
Difficulty: 1.5/5.0
URL: https://oj.leetcode.com/problems/word-search/
Solution
This is a simple problem that can be solved by DFS. The time complexity can be exponential, for example search the word aaaaab
in the matrix shown in the figure.
class Solution {
private:
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
bool exist_helper(const string & word, int pos, const vector<vector<char>>& board, int row, int col,
vector<vector<bool>>&visited){
if (pos == word.size())
return true;
if (!legal(row, col, board)|| visited[row][col] || word[pos] != board[row][col])
return false;
visited[row][col] = true;
for (int idx_dir = 0; idx_dir < 4; ++ idx_dir){
if (exist_helper(word, pos+1, board, row+dir[idx_dir][0], col+dir[idx_dir][1], visited))
return true;
}
visited[row][col] = false;
return false;
}
bool legal(int row, int col, const vector<vector<char>>& board) const{
return (row < board.size() && row >= 0 && col < board[0].size() && col >= 0 );
}
public:
bool exist(vector<vector<char> > &board, string word) {
if (word.size() > board.size() * board[0].size())
return false;
vector<vector<bool>>visited(board.size(), vector<bool>(board[0].size(), 0));
for (int i = 0, nRow = board.size() ; i < nRow; ++ i){
for (int j = 0, nCol = board[i].size(); j < nCol; ++ j){
if (exist_helper(word, 0 ,board, i, j, visited))
return true;
}
}
return false;
}
};