word search

word search

Brute force DFS

This is my favourite. DFS from each point, and search every four directions. When search to a ponint, mark it. When we get back, clear the mark.

`````` 1 class Solution {
2 private:
3 int deltaX[4] = {0,0,-1,1};
4 int deltaY[4] = {1,-1,0,0};
5 public:
6     bool exist(vector<vector<char> > &board, string word) {
7         if ( word.length() == 0 ) {
8             return true;
9         }
10         int n = board.size();
11         if ( !n ) {
12             return false;
13         }
14         int m = board[0].size();
15         if ( !m ) {
16             return false;
17         }
18         if ( n*m < word.length() ) {
19             return false;
20         }
21         for ( int i = 0; i < n; i++ ) {
22             for ( int j = 0; j < m; j++ ) {
23                 if ( DFS(i,j,board,word,0) ) {
24                     return true;
25                 }
26             }
27         }
28         return false;
29     }
30     bool DFS( int x, int y, vector< vector< char > >& board, string word, int index ) {
31         if ( board[x][y] != word[index] ) {
32             return false;
33         }
34         if ( index == word.length()-1 ) {
35             return true;
36         }
37         int n = board.size();
38         int m = board[0].size();
39         char mark = board[x][y];
40         board[x][y] = '.';
41         for ( int i = 0; i < 4; i++ ) {
42             int newX = x+deltaX[i];
43             int newY = y+deltaY[i];
44             if ( newX >= 0 && newX < n && newY >= 0 && newY < m ) {
45                 if ( DFS(newX,newY,board,word,index+1) ) {
46                     return true;
47                 }
48             }
49         }
50         board[x][y] = mark;
51         return false;
52     }
53 };``````