/* * 79. Word Search * 2016-5-12 by Mingyang * 这里的起点就是遍历所有的点，找出这个起点 * 我自己做的时候，用了一个StringBuffer来进行加减，判断条件就是sb和word相等，但是！每次加减sb造成了时间上的浪费 * 这里我们用一个index来就好了，每次完了以后，index+1.这样的话我们就可以通过index和word的长度来判断 * 另外有一个技巧就是index不用自己加加，只用加1，这样不会改变index的本质，不用退回来再减一个了。 * 1.长度标准：所有表格进行遍历，对每一个进行dfs，只要有一个可以就成功了 * 2.可选的范围：没有可选范围，已经规定死了xy轴 * 3.往前走一步：可以往上下左右四个方向分别加1 * 4.后退一步：mark unvisited * 5.特别的case：出界了，访问过了，或者达标了 * 6.关于重复：无 * 这个题目自己在做的时候出了这么几个问题，第一个就是忽略掉了一个条件，就是board[rowindex][colindex] != word.charAt(index) * 另外一个就是忘了把visited改为false，因为开始设为true以后进入下一层，但是从下一层返回来以后无论结果是true还是false * 都应该把visited表还原，因为只有还原才能进行下一个位置的假设。 */ public boolean exist(char[][] board, String word) { int m = board.length; int n = board[0].length; boolean[][] visited = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (dfs4(board, word, 0, i, j, visited)) return true; } } return false; } public boolean dfs4(char[][] board, String word, int index, int rowindex,int colindex, boolean[][] visited) { if (index == word.length()) return true; if (rowindex < 0 || colindex < 0 || rowindex >= board.length|| colindex >= board[0].length) return false; if (visited[rowindex][colindex]) return false; if (board[rowindex][colindex] != word.charAt(index)) return false; visited[rowindex][colindex] = true; boolean res = dfs4(board, word, index + 1, rowindex - 1, colindex,visited) || dfs4(board, word, index + 1, rowindex + 1, colindex, visited) || dfs4(board, word, index + 1, rowindex, colindex + 1, visited) || dfs4(board, word, index + 1, rowindex, colindex - 1, visited); visited[rowindex][colindex] = false; return res; }