算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
## Word Search


### 描述

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where `"adjacent"` cells are those horizontally or vertically neighbouring. The same letter cell may not be used more than once.

For example,
Given board =

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

word = `"ABCCED"`, -> returns `true`,

word = `"SEE"`, -> returns `true`,

word = `"ABCB"`, -> returns `false`.


### 分析

无。


### 代码

{% if book.java %}
{% codesnippet "./code/word-search."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% endif %}

{% if book.cpp %}
```cpp
// Word Search
// 深搜,递归
// 时间复杂度O(n^2*m^2),空间复杂度O(n^2)
class Solution {
public:
bool exist(const vector > &board, const string& word) {
const int m = board.size();
const int n = board[0].size();
vector > visited(m, vector(n, false));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (dfs(board, word, 0, i, j, visited))
return true;
return false;
}
private:
static bool dfs(const vector > &board, const string &word,
int index, int x, int y, vector > &visited) {
if (index == word.size())
return true; // 收敛条件

if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size())
return false; // 越界,终止条件

if (visited[x][y]) return false; // 已经访问过,剪枝

if (board[x][y] != word[index]) return false; // 不相等,剪枝

visited[x][y] = true;
bool ret = dfs(board, word, index + 1, x - 1, y, visited) || // 上
dfs(board, word, index + 1, x + 1, y, visited) || // 下
dfs(board, word, index + 1, x, y - 1, visited) || // 左
dfs(board, word, index + 1, x, y + 1, visited); // 右
visited[x][y] = false;
return ret;
}
};
```
{% endif %}