這是 Leetcode 的一個問題：給定一個 mxn 的字符板網格和一個字串單詞，如果網格中存在單詞，則回傳 true。單詞可以由順序相鄰的單元格的字母構成，其中相鄰的單元格水平或垂直相鄰。同一個字母單元格不能多次使用。
我用 dfs 做了簡單的回溯，這是我的代碼：
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int index = 0;
for(int i = 0; i < board.size(); i ) {
for(int j = 0; j < board[0].size(); j ) {
if(existsUtil(board, index, word, i, j))
return true;
}
}
return false;
}
bool existsUtil(vector<vector<char>> board, int index, string word, int i, int j) {
if(index >= word.length())
return true;
if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[index] || board[i][j] == '0')
return false;
char temp = board[i][j];
board[i][j] = '0';
index = 1;
bool value = existsUtil(board, index, word, i 1, j) || existsUtil(board, index, word, i, j - 1) || existsUtil(board, index, word, i - 1, j) || existsUtil(board, index, word, i, j 1);
board[i][j] = temp;
return value;
}
};
此代碼為更大的輸入提供了 TLE。但是在dfs函式中，如果我通過boardrefrece傳遞引數，也就是如果我pass了vector<vector<char>> &board，就通過了所有的測驗用例。為什么會這樣？
uj5u.com熱心網友回復：
我想，您可以對代碼進行一項優化以僅從 (words[i][j] == word[0]) 的位置開始 dfs
其次，當您每次在遞回呼叫中創建新的二維陣列副本時按值傳遞時回答您的問題，這給出了 TLE。
請參閱我的比 100% JAVA 代碼更快的代碼，希望這會有所幫助！
class Solution {
boolean flag = false;
public boolean exist(char[][] board, String word) {
for(int i = 0;i < board.length;i ){
for(int j = 0;j < board[0].length;j ){
if(board[i][j] == word.charAt(0)){
backtrack(board,word,1,i,j);
if(flag) return true;
}
}
}
return false;
}
void backtrack(char[][] board, String word, int p, int row, int col){
if(board[row][col] > 255)
return;
else if(p > word.length() - 1){
//System.out.println(asf);
flag = true;
return;
}
board[row][col] ^= 256;
//up
if(row > 0 && board[row-1][col] == word.charAt(p)) {
backtrack(board, word, p 1, row - 1, col);
}
//down
if(row < board.length - 1 && board[row 1][col] == word.charAt(p))
backtrack(board,word, p 1,row 1,col);
//left
if(col > 0 && board[row][col-1] == word.charAt(p))
backtrack(board,word, p 1,row,col-1);
//right
if(col < board[0].length - 1 && board[row][col 1] == word.charAt(p))
backtrack(board,word, p 1,row,col 1);
board[row][col] ^= 256;
return;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313565.html
上一篇：演算法-如何找到最高的人塔的高度