文章作者:Tyan
博客:noahsnail.com | CSDN | 简书
1. Description
2. Solution
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int rows = board.size();
int columns = board[0].size();
if(rows * columns < word.length()) {
return false;
}
for(int i = 0; i < rows; i++) {
for(int j = 0; j < columns; j++) {
if(board[i][j] == word[0]) {
if(search(board, word, i, j, 0, rows, columns)) {
return true;
}
}
}
}
return false;
}
bool search(vector<vector<char>>& board, string& word, int i, int j, int current, const int& rows, const int& columns) {
if(i < 0 || i == rows || j < 0 || j == columns || board[i][j] != word[current]) {
return false;
}
board[i][j] -= 60;
current += 1;
if(current == word.length()) {
return true;
}
bool result = search(board, word, i + 1, j, current, rows, columns)
|| search(board, word, i - 1, j, current, rows, columns)
|| search(board, word, i, j + 1, current, rows, columns)
|| search(board, word, i, j - 1, current, rows, columns);
board[i][j] += 60;
return result;
}
};