LeetCode - Word Search

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

 1 // 1CE, 1AC, very smooth.
 2 class Solution {
 3 public:
 4     bool exist(vector<vector<char> > &board, string word) {
 5         n = (int)board.size();
 6         if (n == 0) {
 7             return false;
 8         }
 9         m = (int)board[0].size();
10         word_len = (int)word.length();
11         
12         if (word_len == 0) {
13             return true;
14         }
15         
16         int i, j;
17         for (i = 0; i < n; ++i) {
18             for (j = 0; j < m; ++j) {
19                 if(dfs(board, word, i, j, 0)) {
20                     return true;
21                 }
22             }
23         }
24         return false;
25     }
26 private:
27     int n, m;
28     int word_len;
29     
30     bool dfs(vector<vector<char> > &board, string &word, int x, int y, int idx) {
31         if (x < 0 || x > n - 1 || y < 0 || y > m - 1) {
32             return false;
33         }
34         
35         if (board[x][y] < ‘A‘ || board[x][y] != word[idx]) {
36             // already searched here
37             // letter mismatch here
38             return false;
39         }
40         
41         bool res;
42         if (idx == word_len - 1) {
43             // reach the end of word, success
44             return true;
45         } else {
46             // up
47             board[x][y] -= ‘A‘;
48             res = dfs(board, word, x - 1, y, idx + 1);
49             board[x][y] += ‘A‘;
50             if (res) {
51                 return true;
52             }
53             
54             // down
55             board[x][y] -= ‘A‘;
56             res = dfs(board, word, x + 1, y, idx + 1);
57             board[x][y] += ‘A‘;
58             if (res) {
59                 return true;
60             }
61             
62             // left
63             board[x][y] -= ‘A‘;
64             res = dfs(board, word, x, y - 1, idx + 1);
65             board[x][y] += ‘A‘;
66             if (res) {
67                 return true;
68             }
69             
70             // right
71             board[x][y] -= ‘A‘;
72             res = dfs(board, word, x, y + 1, idx + 1);
73             board[x][y] += ‘A‘;
74             if (res) {
75                 return true;
76             }
77         }
78         // all letters will be within [A-Z], thus I marked a position as ‘searched‘ by setting them to an invalid value.
79         // we have to restore the value when the DFS is done, so their values must still be distiguishable.
80         // therefore, I used an offset value of ‘A‘.
81         // this tricky way is to save the extra O(n * m) space needed as marker array.
82         
83         return false;
84     }
85 };