Wednesday, September 27, 2017

[LeetCode]Word Search


很典型的backtracking问题,从每个cell开始查看能不能找到path match给定的string。假设board size 为m * n,给定string长度为d,时间复杂度Worst case O(m * n * d),空间复杂度O(d)(递归深度),我们在原board上标记当前元素是否被visited过。代码如下:


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;
}
};
view raw Word Search.cpp hosted with ❤ by GitHub

No comments:

Post a Comment