LeetCode 79. 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 neighboring. The same letter cell may not be used more than once.
Example:

board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]

Given word = “ABCCED”, return true.
Given word = “SEE”, return true.
Given word = “ABCB”, return false.
解析：
从二维字符数组检索字符串，判断目标字符是否在二维数组中。
典型的回溯法问题，在每一个节点可以上下左右移动，以当前节点为中心，四个方向进行移动，然后与目标字符进行匹配。题目要求每个cell只使用一次，可以设置visited数组，或者直接在元素组进行更改，处理完成后再进行还原。
具体代码如下：
[cc lang=”C++”]
class Solution {
private:
int w;
int h;
public:
bool exist(vector>& board, string word) {
if(board.empty())
return false;
h = board.size();
w = board[0].size();
for(int i=0; i < w; i++) for(int j=0; j < h; j++) { if(dfs(board, word, 0, i, j)) return true; } return false; } bool dfs(vector>& board, const string& word, int index, int i, int j)
{
if(i <0 || j < 0 || i==w || j == h) return false; if(word[index] != board[j][i]) return false; if(index == word.length() -1) return true; char cur = board[j][i];//记录当前字符 board[j][i] = 0;//标志位 bool found = dfs(board, word, index + 1, i+1, j) || dfs(board, word, index + 1, i, j+1) || dfs(board, word, index + 1, i-1, j) || dfs(board, word, index + 1, i, j-1); board[j][i] = cur;//标志为还原 return found; } }; [/cc]
参考：

花花酱 LeetCode 79. Word Search