參考： https ://leetcode.com/problems/word-search/submissions/
簡要問題陳述：給定一個字符矩陣和一個字串，該字串是否存在于該矩陣中。詳情請參考以上鏈接。
解決方案-1給出了超出的時間限制。
class Solution {
public:
int n;
int m;
bool search(vector<vector<char>>& board, const char* w, int i, int j){
if(i < 0 || i >= m || j < 0 || j >= n || *w != board[i][j] || board[i][j] == '\0') return false;
if(*(w 1) == '\0') return true;
char t = board[i][j];
board[i][j] = '\0';
vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(auto d: dir){
bool temp = search(board, w 1, i d[0], j d[1]);
if(temp) return true;
}
board[i][j] = t;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
m = board.size();
n = board[0].size();
for(int i = 0; i < m; i ){
for(int j = 0; j < n; j ){
if(search(board, word.c_str(), i, j)) return true;
}
}
return false;
}
};
解決方案2作業正常。實際上比大約 93 % 的 C 提交要快
class Solution {
public:
int n;
int m;
bool search(vector<vector<char>>& board, const char* w, int i, int j){
if(i < 0 || i >= m || j < 0 || j >= n || *w != board[i][j] || board[i][j] == '\0') return false;
if(*(w 1) == '\0') return true;
char t = board[i][j];
board[i][j] = '\0';
if(search(board, w 1, i -1, j) || search(board, w 1, i 1, j) || search(board, w 1, i, j-1) || search(board, w 1, i, j 1)) return true;
board[i][j] = t;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
m = board.size();
n = board[0].size();
for(int i = 0; i < m; i ){
for(int j = 0; j < n; j ){
if(search(board, word.c_str(), i, j)) return true;
}
}
return false;
}
};
這兩種解決方案之間的唯一區別是我在搜索函式中遞回呼叫搜索函式的方式。
在solution-1中是：
vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(auto d: dir){
bool temp = search(board, w 1, i d[0], j d[1]);
if(temp) return true;
}
在解決方案 2中，它是：
if(search(board, w 1, i -1, j) || search(board, w 1, i 1, j) || search(board, w 1, i, j-1) || search(board, w 1, i, j 1)) return true;
我認為第二個解決方案就像回圈展開，雖然這部分解釋了為什么第二個比第一個快。只是一個常數因素，它不是更快嗎？我的意思是漸近地它們是相似的。我很驚訝回圈展開導致我的解決方案從 TLE 變為比 93% 更快的解決方案。
基本上，我的問題是，回圈展開是第二個解決方案如此之快的唯一原因，還是我遺漏了什么？
uj5u.com熱心網友回復：
我不確定auto型別的時間復雜度！但是，如果您從遞回函式中洗掉 2D 向量構造，而不是auto使用正常的基于索引的回圈來訪問向量，那么您將通過時間限制。
class Solution {
public:
int n;
int m;
vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool search(vector<vector<char>>& board, const char* w, int i, int j){
if(i < 0 || i >= m || j < 0 || j >= n || *w != board[i][j] || board[i][j] == '\0') return false;
if(*(w 1) == '\0') return true;
char t = board[i][j];
board[i][j] = '\0';
for(int r=0; r<4; r ){
bool temp = search(board, w 1, i dir[r][0], j dir[r][1]);
if(temp) return true;
}
board[i][j] = t;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
m = board.size();
n = board[0].size();
for(int i = 0; i < m; i ){
for(int j = 0; j < n; j ){
if(search(board, word.c_str(), i, j)) return true;
}
}
return false;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/488646.html