Last Updated on 2022-11-24 by Clay
題目
Given an m x n
grid of characters board
and a string word
, return true
if word
exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false
Constraints:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board
andword
consists of only lowercase and uppercase English letters.
Follow up: Could you use search pruning to make your solution faster with a larger board
?
題目給定一個棋盤空間以及一組文字,我們要判斷的就是文字是否有出現在棋盤上。當然,我們不能走重複的位置。
解題紀錄
這題我的解法是很純粹地用 DFS 下去解,不過雖然在 C++ 時通過了、但是在 Python 時卻超過時限... 可能有哪邊需要改進。
DFS 遞迴式裡,第一個要判斷的是文字 word
是否已經判斷到最後一個字元了。如果已經判斷到最後一個字元,則回傳 true
。
接著是判斷當前棋盤上要判斷的點,是否超出了邊界。
最後,則是判斷棋盤上當前要判斷的文字,跟當前要匹配的文字 word
中的字元是否一致。
C++ 範例程式碼
class Solution {
public:
bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
// If matching is finished
if (k >= word.size()) {
return true;
}
// If current position (i, j) is out of boundary
if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) {
return false;
}
// If the current character is mismatch the word
if (board[i][j] != word[k]) {
return false;
}
// Change the current board to prevent the DFS check the same character again
char temp = board[i][j];
board[i][j] = 0;
// DFS
bool isExisted = dfs(board, word, i+1, j, k+1) || dfs(board, word, i-1, j, k+1) || dfs(board, word, i, j+1, k+1) || dfs(board, word, i, j-1, k+1);
// Recovery
board[i][j] = temp;
return isExisted;
}
bool exist(vector<vector<char>>& board, string word) {
// Iter
for (int i=0; i<board.size(); ++i) {
for (int j=0; j<board[0].size(); ++j) {
if (dfs(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
};