LeetCode: 79. Word Search
- tags: LeetCode
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
backtracking(board, word, 0, 0);
return res;
}
private:
string track;
bool res = false;
enum Direction {
right,
down,
up,
left,
};
/**
* @param dir: 0: right, 1: down, 2: up, 3: left
*/
void backtracking(vector<vector<char>>& board, string word, int row, int col) {
if (track == word || res) {
res = true;
return;
}
for (int i = row; i < board.size(); i++) {
for (int j = col; j < board[i].size(); j++) {
auto directions = get_next_directions(board, i, j);
if (directions.size() == 0) {
return;
}
for (auto d: directions) {
int r, c;
track.push_back(board[i][j]);
std::tie(r, c) = next_char_pos(board, row, col, d);
if (word.find(track) == 0) {
backtracking(board, word, r, c);
}
track.pop_back();
}
}
}
}
vector<Direction> get_next_directions(vector<vector<char>>& board, int row, int col) {
vector<Direction> r;
if (col < board[row].size() - 1) {
r.push_back(right);
}
if (row < board.size() - 1) {
r.push_back(down);
}
if (row > 0) {
r.push_back(up);
}
if (col > 0) {
r.push_back(left);
}
return r;
}
tuple<int, int> next_char_pos(vector<vector<char>>& board, int row, int col, Direction dir) {
switch(dir) {
case right:
col++;
break;
case left:
col--;
break;
case up:
row--;
break;
case down:
row++;
break;
}
tuple<int, int>r(row, col);
return r;
}
};
失败的用例：
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCB"
因为方向往回走导致，应该规避方向往回走。通过一个 set 来跟踪位置，防止进入前面的位置：
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
backtracking(board, word, 0, 0);
return res;
}
private:
string track;
bool res = false;
set<tuple<int, int>> pos;
enum Direction {
right,
down,
up,
left,
};
/**
* @param dir: 0: right, 1: down, 2: up, 3: left
*/
void backtracking(vector<vector<char>>& board, string word, int row, int col) {
if (track == word || res) {
res = true;
return;
}
for (int i = row; i < board.size(); i++) {
for (int j = col; j < board[i].size(); j++) {
auto directions = get_next_directions(board, i, j);
if (directions.size() == 0) {
return;
}
for (auto d: directions) {
tuple<int, int> p (i, j);
if (pos.find(p) != pos.end()) {
continue;
}
pos.insert(p);
track.push_back(board[i][j]);
int r, c;
std::tie(r, c) = next_char_pos(board, row, col, d);
if (word.find(track) == 0) {
backtracking(board, word, r, c);
}
track.pop_back();
pos.erase(p);
}
}
}
}
vector<Direction> get_next_directions(vector<vector<char>>& board, int row, int col) {
vector<Direction> r;
if (col < board[row].size() - 1) {
r.push_back(right);
}
if (row < board.size() - 1) {
r.push_back(down);
}
if (row > 0) {
r.push_back(up);
}
if (col > 0) {
r.push_back(left);
}
return r;
}
tuple<int, int> next_char_pos(vector<vector<char>>& board, int row, int col, Direction dir) {
switch(dir) {
case right:
col++;
break;
case left:
col--;
break;
case up:
row--;
break;
case down:
row++;
break;
}
tuple<int, int>r(row, col);
return r;
}
};
失败的用例：
[["a"]]
"a"
代码逻辑有问题，修正后：
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
backtracking(board, word, 0, 0);
return res;
}
private:
string track;
bool res = false;
set<tuple<int, int>> pos;
enum Direction {
right,
down,
up,
left,
};
/**
* @param dir: 0: right, 1: down, 2: up, 3: left
*/
void backtracking(vector<vector<char>>& board, string word, int row, int col) {
if (track == word || res) {
res = true;
return;
}
for (int i = row; i < board.size(); i++) {
for (int j = col; j < board[i].size(); j++) {
tuple<int, int> p (i, j);
if (pos.find(p) != pos.end()) {
continue;
}
pos.insert(p);
track.push_back(board[i][j]);
if (track == word || res) {
res = true;
return;
}
if (word.find(track) == 0) {
auto directions = get_next_directions(board, i, j);
for (auto d: directions) {
int r, c;
std::tie(r, c) = next_char_pos(board, row, col, d);
backtracking(board, word, r, c);
}
}
track.pop_back();
pos.erase(p);
}
}
}
vector<Direction> get_next_directions(vector<vector<char>>& board, int row, int col) {
vector<Direction> r;
if (col < board[row].size() - 1) {
r.push_back(right);
}
if (row < board.size() - 1) {
r.push_back(down);
}
if (row > 0) {
r.push_back(up);
}
if (col > 0) {
r.push_back(left);
}
return r;
}
tuple<int, int> next_char_pos(vector<vector<char>>& board, int row, int col, Direction dir) {
switch(dir) {
case right:
col++;
break;
case left:
col--;
break;
case up:
row--;
break;
case down:
row++;
break;
}
tuple<int, int>r(row, col);
return r;
}
};
以下测试用例无法通过：
[["a","b"]]
"ba"
调整代码后（进入下一个节点的 row/col 没用 i/j）:
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
backtracking(board, word, 0, 0);
return res;
}
private:
string track;
bool res = false;
set<tuple<int, int>> pos;
enum Direction {
right,
down,
up,
left,
};
/**
* @param dir: 0: right, 1: down, 2: up, 3: left
*/
void backtracking(vector<vector<char>>& board, string word, int row, int col) {
cout << track << endl;
if (track == word || res) {
res = true;
return;
}
for (int i = row; i < board.size(); i++) {
for (int j = col; j < board[i].size(); j++) {
tuple<int, int> p (i, j);
if (pos.find(p) != pos.end()) {
continue;
}
pos.insert(p);
track.push_back(board[i][j]);
if (track == word) {
res = true;
return;
}
if (word.find(track) == 0) {
auto directions = get_next_directions(board, i, j);
for (auto d: directions) {
int r, c;
std::tie(r, c) = next_char_pos(board, i, j, d);
backtracking(board, word, r, c);
}
}
track.pop_back();
pos.erase(p);
}
}
}
vector<Direction> get_next_directions(vector<vector<char>>& board, int row, int col) {
vector<Direction> r;
if (col < board[row].size() - 1) {
r.push_back(right);
}
if (row < board.size() - 1) {
r.push_back(down);
}
if (row > 0) {
r.push_back(up);
}
if (col > 0) {
r.push_back(left);
}
return r;
}
tuple<int, int> next_char_pos(vector<vector<char>>& board, int row, int col, Direction dir) {
switch(dir) {
case right:
col++;
break;
case left:
col--;
break;
case up:
row--;
break;
case down:
row++;
break;
}
tuple<int, int>r(row, col);
return r;
}
};
此时的失败用例：
[["a","b"],["c","d"]]
"abcd"
改成如果位置已经存在则返回可以通过:
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
backtracking(board, word, 0, 0);
return res;
}
private:
string track;
bool res = false;
set<tuple<int, int>> pos;
enum Direction {
right,
down,
up,
left,
};
/**
* @param dir: 0: right, 1: down, 2: up, 3: left
*/
void backtracking(vector<vector<char>>& board, string word, int row, int col) {
if (track == word || res) {
res = true;
return;
}
for (int i = row; i < board.size(); i++) {
for (int j = col; j < board[i].size(); j++) {
tuple<int, int> p (i, j);
if (pos.find(p) != pos.end()) {
return; // <--------- here
}
pos.insert(p);
track.push_back(board[i][j]);
if (word.find(track) == 0) {
auto directions = get_next_directions(board, i, j);
if (track == word) {
res = true;
return;
}
for (auto d: directions) {
int r, c;
std::tie(r, c) = next_char_pos(board, i, j, d);
backtracking(board, word, r, c);
}
}
track.pop_back();
pos.erase(p);
}
}
}
vector<Direction> get_next_directions(vector<vector<char>>& board, int row, int col) {
vector<Direction> r;
if (col < board[row].size() - 1) {
r.push_back(right);
}
if (row < board.size() - 1) {
r.push_back(down);
}
if (row > 0) {
r.push_back(up);
}
if (col > 0) {
r.push_back(left);
}
return r;
}
tuple<int, int> next_char_pos(vector<vector<char>>& board, int row, int col, Direction dir) {
switch(dir) {
case right:
col++;
break;
case left:
col--;
break;
case up:
row--;
break;
case down:
row++;
break;
}
tuple<int, int>r(row, col);
return r;
}
};
但是在下面测试用例失败了：
[["b"],["a"],["b"],["b"],["a"]]
"baa"
简单的过滤掉：
if (board.size() > 0 && board[0].size() == 1) {
string s;
for (int i = 0; i < board.size(); i++) {
s.push_back(board[0][0]);
}
return s.find(word) != string::npos;
}
现在下面失败了：
[["a","a","b","a","a","b"],["a","a","b","b","b","a"],["a","a","a","a","b","a"],["b","a","b","b","a","b"],["a","b","b","a","b","a"],["b","a","a","a","a","b"]]
"bbbaabbbbbab"
经过仔细推敲后：
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[i].size(); j++) {
backtracking(board, word, i, j);
}
}
return res;
}
private:
string track;
bool res = false;
set<tuple<int, int>> pos;
enum Direction {
right,
down,
up,
left,
};
/**
* @param dir: 0: right, 1: down, 2: up, 3: left
*/
void backtracking(vector<vector<char>>& board, string word, int row, int col) {
tuple<int, int> p (row, col);
if (pos.find(p) != pos.end()) {
return; // <--------- here
}
pos.insert(p);
track.push_back(board[row][col]);
if (track == word) {
cout << track << endl;
res = true;
return;
}
if (res) {
return;
}
if (word.find(track) == 0) {
cout << row << ", " << col << endl;
auto directions = get_next_directions(board, row, col);
for (auto d: directions) {
int r, c;
std::tie(r, c) = next_char_pos(board, row, col, d);
cout << " " << r << "," << c << endl;
backtracking(board, word, r, c);
}
}
track.pop_back();
pos.erase(p);
}
vector<Direction> get_next_directions(vector<vector<char>>& board, int row, int col) {
vector<Direction> r;
if (col < board[row].size() - 1) {
r.push_back(right);
}
if (row < board.size() - 1) {
r.push_back(down);
}
if (row > 0) {
r.push_back(up);
}
if (col > 0) {
r.push_back(left);
}
return r;
}
tuple<int, int> next_char_pos(vector<vector<char>>& board, int row, int col, Direction dir) {
switch(dir) {
case right:
col++;
break;
case left:
col--;
break;
case up:
row--;
break;
case down:
row++;
break;
}
tuple<int, int>r(row, col);
return r;
}
};
下面用例会导致处理事件过长：
[["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"]]
"AAAAAAAAAAAAAAB"
测试用例快照:
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCCED"
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"SEE"
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCB"
[["a"]]
"a"
[["a","b"]]
"ba"
[["a","b"],["c","d"]]
"dbac"
[["a","b"],["c","d"]]
"abcd"
[["a","a","a","a"],["a","a","a","a"],["a","a","a","a"]]
"aaaaaaaaaaaaa"
[["b"],["a"],["b"],["b"],["a"]]
"baa"
[["a"]]
"ab"
[["a","a","b","a","a","b"],["a","a","b","b","b","a"],["a","a","a","a","b","a"],["b","a","b","b","a","b"],["a","b","b","a","b","a"],["b","a","a","a","a","b"]]
"bbbaabbbbbab"
[["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"]]
"AAAAAAAAAAAAAAB"