leetcode-79-word search

题目

给定二维字符数组,寻找数组中是否存在某个单词。要求该word在数组中的位置是连续的。且位置不能重复。注:只能上下左右遍历字符。

分析

举例分析:
对于: [
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]

  • word = “ABCCED”, -> returns true,
  • word = “SEE”, -> returns true,
  • word = “ABCB”, -> returns false.

显然利用DFS进行遍历。对于遍历过的数据进行标记。

C++代码实现

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
30
31
class Solution {
public:
bool (vector<vector<char> >& board, string word) {
int rows = board.size();
int cols = board[0].size();
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(isFound(board, word, 0, i, j))
return true;
}
}
return false;
}

bool isFound(vector<vector<char> > &board, string word, int len, int i, int j){
if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] == '