-
Notifications
You must be signed in to change notification settings - Fork 0
/
WordSearch.cpp
29 lines (27 loc) · 924 Bytes
/
WordSearch.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
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,i,j,0,word))
return true;
}
}
return false;
}
bool exist(vector<vector<char>> &board,int i,int j,int pos,string word){
if(i<0||i>=board.size()||j<0||j>=board[0].size()) return false;
if(board[i][j] != word[pos]) return false;
if(pos + 1 == word.size()) return true;
char temp = board[i][j];
board[i][j] = '0';
bool result = exist(board,i-1,j,pos+1,word) || exist(board,i+1,j,pos+1,word)||
exist(board,i,j-1,pos+1,word) || exist(board,i,j+1,pos+1,word);
board[i][j] = temp;
return result;
}
};