79. 单词搜索

这题要使用dfs和剪枝class Solution { public boolean exist(char[][] board, String word) { char[] words word.toCharArray(); for (int i 0; i board.length; i) { for (int j 0; j board[0].length; j) { if (dfs(board, words, i, j ,0)) return true; } } return false; } public boolean dfs(char[][] board, char[] word, int i, int j, int k) { //如果超出边界或者字母不匹配要剪枝,返回上一层 if (i board.length || i 0 || j 0 || j board[0].length || board[i][j] ! word[k]) return false; //如果匹配的字数够了 if (k word.length - 1) return true; //先将该字母变成空,防止之后还会访问到这个字母 board[i][j] \0; //往四个方向去扩展,只要有一条可以都行 boolean res dfs(board, word, i 1, j, k 1) ||dfs(board, word, i - 1, j, k 1) || dfs(board, word, i, j 1, k 1) || dfs(board, word, i , j - 1, k 1); //结束还原原来的字母 board[i][j] word[k]; return res; } }