Given a 2D board and a word, find if the word exists in the grid.
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.
Example:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = "ABCCED", return true. Given word = "SEE", return true. Given word = "ABCB", return false.
A:
---------------------------------- 3 rd pass , 用一个2D array 记录是否visit过---------- 然后就是简单的dfs了----------------和第二遍一样，但是，没有这里，检测了输入m,n是否为0 的情况，因此，多写了几行。------------class Solution { public: bool exist(vector<vector<char>>& board, string word) { int m = board.size(), n = board[0].size(); vector<vector<bool>> flags; for(int i =0;i<m;++i) { vector<bool> tmp(n,false); flags.push_back(tmp); } for(int i =0;i<m;++i) for(int j=0; j<n;++j) if(dfs(board, flags, word,0, i,j)) return true; return false; } private: bool dfs(vector<vector<char>>& board, vector<vector<bool>> & A, string word, int index,int i, int j) { int m = A.size(), n = A[0].size(); if(board[i][j] == word[index] && A[i][j]==false) { A[i][j] = true; if(++index >= word.length()) // if board==[[a]], following 4 cannot go further return true; if(i>0 && dfs(board, A, word, index,i-1,j)) // go up return true; if(i+1<m && dfs(board, A, word, index, i+1, j)) // go down return true; if(j>0 && dfs(board, A, word, index, i, j-1)) // go left return true; if(j+1<n && dfs(board, A, word, index, i, j+1)) // go right return true; A[i][j] = false; } return false; } };
错误：
在dfs中，我们已经假设了word不为空，就需要在match当前char之后，再看现在是否start 位置还没出界--------------------------------------------------第二遍 ---- 思路同上，但是没有用Stack-------------------
就是设立了一个2D的标识。记录是否被存下。
public class Solution {
public boolean exist(char[][] board, String word) {
if(board == null || word == null || board.length==0|| board[0].length == 0)
return false;
int m = board.length,n = board[0].length;
boolean[][] A = new boolean[m][n];
for(int i =0;i<m;i++){
for(int j =0; j<n;j++)
if(helper(board,A,i,j,word))
return true;
}
return false;
}
private boolean helper(char[][] board,boolean[][] A, int i ,int j , String word){
if(word.length()==0)
return true;
if(i<0||i>=board.length || j<0 || j>= board[0].length)
return false;
if(A[i][j] == false && word.charAt(0) == board[i][j]){
A[i][j] = true; // set the signal
String tmp = word.substring(1);
if( helper(board,A,i-1,j,tmp) ||helper(board,A,i+1,j,tmp) || helper(board,A,i,j-1,tmp) || helper(board,A,i,j+1,tmp) )
return true;
A[i][j] = false;
}
return false;
}
}
----------------错误---------------
开头的这句话
boolean[][] hasVisited = new boolean[board.length][board[0].length];一开始，给写到 双重循环里面去了。导致超时，哎， 一晚上，就因为这个被stuck住， 都没干别的。 郁闷~~~~~~~~不值得啊
------------------------------------------- 1 st pass ---------------------------------------------------------------
增强的 DFS ,
思路就是，通过另一个visitedBoard来记录该节点是否所有的neighbor都被visited 过。如果没有，则增加一个，如果有。 则pop出来该节点。并将其父节点（stack.peak()） 的visitBoard 的数量增加1.
-----------------
一个关键的问题就是：我们dfs的时候，设置了停止条件是： start>word.length(); 但是这样是不对的。
因为，有可能我们的下标没有可能出界的。例如输入时“s”，"s"。
因此，我们要检测是否是最后一个char
Mistakes:
1： findStringIndex的考虑的时候， 例如当问题中给出的例子，”ABCB“的时候， 当找到C的时候， findStringIndex 的值是3了， 而，在我们别的变量里面，都是index, 而不是match的数量，因此，我们这里应该是2的。 ------------------------------哎，你个糊涂蛋，------------
if( lastFindCharIndex >= word.length() -1){// if match the last char
return true; // we just find the whole word
}
你这里，是考虑的当已经找到了最后一个的情况， 然后，我们这时候，在下面的四种情况中，是 加了1 的， 那么，就word.length() 就不应该减一啊。
-------------哦， 当初想减一，是考虑到，后面的4种情况监测的时候， 要加1 啊
晕，你SB， 上面全错了， 那样写是对的，只是因为，题目要求 may NOT use the same letter more than once. --------------------看题不谨慎啊！！！！！！！！
2：在利用tmpBoard的时候，忘了把第一个字母全部变成neverUsedChar, 导致输入{"aa"} "aaa"的时候，结果是find。
3: 当一条路走不通的时候，应该把走过的路，都回溯成原来的样子， 以待别走法。
4： 不能用BFS， 那样的话， 就会先把周围match的点的颜色先该了。
5： 自己还是因为，对DFS的理解不够深入导致，回去多看看类似的DFS，BFS的 题目吧。
Learned:
1: ArrayList<int[]> firstIndexes = new ArrayList<int[]>(); 这样是可以的， 而不是非得用Integer 取代int. (自己是受以前的代码的影响）
2:
No comments:
Post a Comment