30
07/2015
[LeetCode] Word Search
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.
For example,
Given board =
[ ["ABCE"], ["SFCS"], ["ADEE"] ]word =
"ABCCED", -> returns true,word =
"SEE", -> returns true,word =
"ABCB", -> returns false.解题思路：
回溯法。用一个二维数组标记是否已经访问，然后朝上下左右四个方向进行扩展即可。
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int len = word.length();
if(len==0){
return true;
}
int m = board.size();
if(m==0){
return false;
}
int n = board[0].size();
if(n==0){
return false;
}
vector<vector<bool>> flag(m, vector<bool>(n, false));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(helper(board, flag, i, j, 0, word)){
return true;
}
}
}
return false;
}
bool helper(vector<vector<char>>& board, vector<vector<bool>>& flag, int i, int j, int index, string& word){
if(index>=word.length()){
return true;
}
int m = board.size();
int n = board[0].size();
if(i<0 || i>=m || j<0 || j>=n || flag[i][j] || board[i][j]!=word[index]){
return false;
}
flag[i][j] = true;
bool result = helper(board, flag, i+1, j, index + 1, word) ||
helper(board, flag, i, j+1, index + 1, word) ||
helper(board, flag, i-1, j, index + 1, word) ||
helper(board, flag, i, j-1, index + 1, word);
flag[i][j] = false;
return result;
}
};转载请注明：康瑞部落 » [LeetCode] Word Search
0 条评论