很典型的backtracking问题,从每个cell开始查看能不能找到path match给定的string。假设board size 为m * n,给定string长度为d,时间复杂度Worst case O(m * n * d),空间复杂度O(d)(递归深度),我们在原board上标记当前元素是否被visited过。代码如下:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
bool exist(vector<vector<char>>& board, string word) { | |
int m = board.size(), n = m? board[0].size(): 0; | |
for(int i = 0; i < m; ++i) | |
{ | |
for(int j = 0; j < n; ++j) | |
{ | |
if(backtrack(board, word, 0, i, j)) | |
return true; | |
} | |
} | |
return false; | |
} | |
private: | |
bool backtrack(vector<vector<char>>& board, const string& word, int idx, int x, int y) | |
{ | |
if(idx == word.size() - 1 && board[x][y] == word[idx]) | |
return true; | |
int m = board.size(), n = m? board[0].size(): 0; | |
char c = word[idx], tmp = board[x][y]; | |
vector<pair<int, int>> dirs = {{1, 0},{-1, 0},{0, 1},{0, -1}}; | |
if(board[x][y] == c) | |
{ | |
board[x][y] = '.'; | |
for(auto& dir : dirs) | |
{ | |
int i = x + dir.first; | |
int j = y + dir.second; | |
if(i >= 0 && i < m && j >= 0 && j < n && board[i][j] != '.' && backtrack(board, word, idx + 1, i, j)) | |
return true; | |
} | |
board[x][y] = tmp; | |
} | |
return false; | |
} | |
}; |
No comments:
Post a Comment