79. Word Search
1.問題
給予一個陣列, 檢查路徑是否存在

2.想法
提問:
function header, parameter
test input
說明想法
路徑問題, 判斷是否有路徑存在時, 可以由一點(row, col)往上下左右擴散
base case:
如果index == word.length()時回傳true
如果row, col超過範圍, 或是曾經走訪過, 或是當前走到的字母不等於目標, 則回傳false
測試計算複雜度
3.程式碼
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(search(board, visited, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private:
bool search(vector<vector<char>>& board, vector<vector<bool>>& visited, string word, int row, int col, int index){
if (index == word.length()) {
return true;
}
if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || visited[row][col] || board[row][col] != word[index]) {
return false;
}
visited[row][col] = true;
if(search(board, visited, word, row + 1, col, index + 1)) {
return true;
}
if(search(board, visited, word, row - 1, col, index + 1)) {
return true;
}
if(search(board, visited, word, row, col + 1, index + 1)) {
return true;
}
if(search(board, visited, word, row, col - 1, index + 1)) {
return true;
}
visited[row][col] = false;
return false;
}
};
Last updated