這題也是我兩年前寫的, 我本來意氣風法用dfs秒解
結果一直tle, 我就在想沒天理啊QQQQ
bool top = dfs(b, s ,i - 1, j);;
bool down = dfs(b, s ,i + 1, j);
bool right = dfs(b,s, i, j + 1);
bool left = dfs(b, s, i, j - 1);
跟
bool res = dfs(b, s, i -1, j) ||dfs(b, s ,i + 1, j) || dfs(b,s, i, j + 1)|| dfs(b, s, i, j - 1);問題出在這個地方, 很巧妙啊 用or如果前面的判斷是已經是true了, 我後續的都不會去管他,
但我上面會每個都要求做完, 導致一直TLE
非常冤望, 但也深刻
class Solution {
public:
bool dfs(vector<vector<char>> &b, string &word, int i, int j){
if(word.size() == 0) return true;
if(i < 0 || j < 0 || i >= b.size() || j >=b[0].size() || b[i][j] != word[0]) return false;string s = word.substr(1);
char c = b[i][j];
b[i][j] = '*';
bool res = dfs(b, s, i -1, j) ||dfs(b, s ,i + 1, j) || dfs(b,s, i, j + 1)|| dfs(b, s, i, j - 1);
b[i][j] = c;
return res;
}
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
for(int i = 0; i < m ; i++){
for(int j = 0; j < n; j++){
if(dfs(board, word,i, j)){
return true;
}
}
}
return false;
}
};
後記, 過了一年後就把這個方法給忘記了, 得重新找回
時間複雜度為O(M * N * dfs compilxity) == O(M * N * M * N)
