文章作者:Tyan 博客:noahsnail.com | | 简书
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;
}
};
Reference
https://leetcode.com/problems/word-search/description/