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.
For example,
Given board
=
[
["ABCE"],
["SFCS"],
["ADEE"]
]
word = "ABCCED",
-> returns true,
word = "SEE", -> returns true,
word = "ABCB",
-> returns false.
Solution: DFS. (For ‘visited‘, using two-dimensional array will be faster than vector<vector>.[90+ms->50+ms])
1 class Solution { 2 public: 3 typedef vector<vector<char> > VECTOR2D; 4 5 bool exist(VECTOR2D &board, string word) { 6 int N = board.size(), M = board[0].size(); 7 VECTOR2D avail(N, vector<char>(M, ‘o‘)); 8 for (int i = 0; i < N; ++i) 9 for (int j = 0; j < M; ++j) 10 if (existRe(board, word, 0, i, j, avail)) 11 return true; 12 return false; 13 } 14 15 bool existRe(const VECTOR2D &board, const string &word, int deep, int i, int j, VECTOR2D &avail) 16 { 17 int N = board.size(), M = board[0].size(); 18 if (deep == word.size()) return true; 19 if (i < 0 || i >= N || j < 0 || j >= M) return false; 20 if (board[i][j] != word[deep] || avail[i][j] == ‘x‘) return false; 21 22 avail[i][j] = ‘x‘; 23 if (existRe(board, word, deep + 1, i-1, j, avail)) return true; 24 if (existRe(board, word, deep + 1, i+1, j, avail)) return true; 25 if (existRe(board, word, deep + 1, i, j-1, avail)) return true; 26 if (existRe(board, word, deep + 1, i, j+1, avail)) return true; 27 avail[i][j] = ‘o‘; 28 29 return false; 30 } 31 };
原文：http://www.cnblogs.com/zhengjiankang/p/3679648.html