回溯法练习:
给定一组二维字符，对于每个字符只能向上下左右某个方向走，求是否有路径经过的字符串恰好是给定的字符串(leetcode79)：
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.思路：回溯法的练习题。遍历每一个位置，对于每个位置，判断其是否等于字符串当前的字符，然后其可以向上左下右走(存在)，判断是否等于下一个位置的字符，以此递归，递归的出口是到达字符串的最后一个字符且平面字符等于该字符。同时，题目要求不能重复走某个位置，所以要记录当前位置是否走过。这题用到回溯的思想是每个位置board[i][j]都走上右下左，四个方向都不符合的话就回溯到board[i][j]的上一位置，再找其的下一个方向。
public class L79WordSearch { int[][] path ={{0,1},{1,0},{0,-1},{-1,0}}; boolean[][] visit ; public static void main(String[] args) { char[][] board ={{'a','b'}}; // { // {'A','B','C','E'}, // {'S','F','C','S'}, // {'A','D','E','E'} // }; System.out.println(new L79WordSearch().exist(board, "ba")); } public boolean exist(char[][] board, String word) { visit = new boolean[board.length][board[0].length]; boolean res = false; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if(hasPath(board, word, i, j, 0)){ res = true; } } } return res; } public boolean hasPath(char[][] board, String word, int x, int y, int index){ System.out.println(x+" "+y+" "+board[x][y] +" "+(index)); if(index==word.length()-1){ return board[x][y] == word.charAt(index); } if(board[x][y] == word.charAt(index)){ for (int i = 0; i < 4; i++) { if(inArea(board, x+path[i][0], y+path[i][1]) && !visit[x+path[i][0]][ y+path[i][1]]){ // System.out.println(board[x+path[i][0]][y+path[i][1]] +" "+(index+1)); if(hasPath(board, word, x+path[i][0], y+path[i][1], index+1)){ return true; } } } visit[x][y] = false; } return false; } public boolean inArea(char[][] board,int x,int y){ return x<=board.length-1 && y<=board[0].length-1 && x>=0 && y>=0; } }