The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[ ["ABCE"], ["SFCS"], ["ADEE"] ]word =
"ABCCED", -> returns true,word =
"SEE", -> returns true,word =
"ABCB", -> returns false.这个题目！！！ 还是老套地用BFS去搜Graph, BFS不仅代码很长，而且很不适合做仅仅是搜索的问题，如果要找最短路径还可能会考虑BFS去做。 所以这个题目直接用短小简单的DFS来写很快，而且不容易出错。 一直都尝试用BFS去做这样的题目，可能是对自己的DFS的掌握没有信心， 其实这个题目转化成图，也可以看成是一颗DFS搜索树，层数是string的长度，每一层的分支数是该点上下左右的可能取值，最多4叉，
Solu1:
BFS 去搜上下左右，但是这题里BFS是不是存在不能找到的路径？？？因此不能用BFS来做？？下面的solu是不能通过测试的，因为BFS可能存在两个可能路径时，有可能有一条路径走不到。
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
//sanity check
if (board.size() == 0 || board[0].size() == 0) return false;
if (word.size() == 0) return false;
vector<int> p;
for ( int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (board[i][j] == word[0]) {
p.push_back(i * board[0].size() + j);
}
}
}
int w = 1;
for (int i = 0; i < p.size(); i++) {
int x = p[i] / board[0].size();
int y = p[i] % board[0].size();
queue<pair<int, int>> pqueue;
set<int> pset;
pqueue.push(make_pair(x, y));
// pset.insert(p[i]);
while (!pqueue.empty()) {
pair<int, int> tmp = pqueue.front();
int x1 = tmp.first;
int y1 = tmp.second;
pqueue.pop();
if (w == word.size()) return true;
if (pset.find((x1+1) * board[0].size() + y1) == pset.end()){
if (x1 + 1 < board.size() && w < word.size() && board[x1+1][y1] == word[w]) {
pqueue.push(make_pair(x1+1, y1));
pset.insert((x1+1) * board[0].size() + y1);
}
}
if (pset.find((x1) * board[0].size() + y1+1) == pset.end()){
if (y1 + 1 < board[0].size() && w < word.size() && board[x1][y1+1] == word[w]) {
pqueue.push(make_pair(x1, y1+1));
pset.insert((x1) * board[0].size() + y1+1);
}
}
if (pset.find((x1-1) * board[0].size() + y1) == pset.end()){
if (x1 - 1 >= 0 && w < word.size() && board[x1-1][y1] == word[w]) {
pqueue.push(make_pair(x1-1, y1));
pset.insert((x1-1) * board[0].size() + y1);
}
}
if (pset.find((x1) * board[0].size() + y1-1) == pset.end()){
if (y1 - 1 >= 0 && w < word.size() && board[x1][y1-1] == word[w]) {
pqueue.push(make_pair(x1, y1-1));
pset.insert((x1) * board[0].size() + y1-1);
}
}
w++;
}
w = 1;
}
return false;
}
};
Solu2:
DFS: DFS 跟BFS一样，也需要对访问过的元素进行标记，在这里，可以直接将访问过的元素设置为‘#’，DFS过后又将其还原成原来的符号。
其实对于图的DFS遍历，跟树的DFS遍历是一样的，只要能够将DFS遍历树画出来，有几层每一层有几个叉，很容易实现代码。 DFS的返回值可以有不同的含义，这里DFS的返回值是以一个起点能够走到终点的bool值。
通常利用DFS来遍历DFS树或者二维矩阵图来找路径 + mark visit 的思路：
有两种mark的方法：
1. visited mark => BFS, 只要一个node到达了，就mark，以后的DFS均不能访问这个Node
2. backtracking: 只在一条DFS path上面mark，当一条路径向上一层返回时unmark这个node，这个node可以被其他路径重复访问。 一般这种mark visited的方法用于查找所有的路径。BFS由于只有第一种mark的方法，所以BFS只能找到一个start 到 一个end的最短路径，但是不能找到一个start 到一个end的所有path，即不能找到指定的某一条path。
所以这个题目中，用BFS做是错误的做法，指定的路径BFS是不能找到的，BFS只适合于1.判断两点之间有没有路径，能否到达 2. 找两点之间最短路径。
//what the DFS do in current level
//1. mark visited
//2. how many braches in this level
//3. all these braches are valid?? conditions to enter to the next level through that branch
//4. return what to the parent
class Solution {
private:
bool DFS(int w, vector<vector<char>>& board, string word, int i, int j) {
//base case
if (w == word.size()-1) {
return true;
}
//4 branches, has to call DFS 4 times
char tmp = board[i][j];
board[i][j] ='#';
if (i + 1 < board.size() && board[i+1][j] == word[w+1]) {
if(DFS(w+1, board, word, i+1, j)) return true;
}
if (j + 1 < board[0].size() && board[i][j+1] == word[w+1]) {
if(DFS(w+1, board, word, i, j+1)) return true;
}
if (i - 1 >= 0 && board[i-1][j] == word[w+1]) {
if(DFS(w+1, board, word, i-1, j)) return true;
}
if (j - 1 >= 0 && board[i][j-1] == word[w+1]) {
if(DFS(w+1, board, word, i, j-1)) return true;
}
board[i][j] = tmp;
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
//sanity check
if (board.size() == 0 || board[0].size() == 0) return false;
if (word.size() == 0) return false;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (board[i][j] == word[0] && DFS(0, board, word, i, j)) {
return true;
}
}
}
return false;
}
};
No comments:
Post a Comment