Java学习手册：（数据结构与算法-数组）Word Search（leetcode79）

题目给定一个二维平面的字母和一个单词看是否可以在这个二维平面上找到该单词。其中找到这个单词的规则是从一个字母出发可以横向或者纵向连接二维平面上的其他字母。同一个位置的字母只能使用一次。输入1二维数组{ {A,B,C,E}, {S,F,C,S}, {A,D,E,E}}2输入/输出“ABCCED”→true“SEE”→true“ABCB”→false思路递归代码如下package com.haobi; public class WordSearch { private static int m, n; private static int d[][] {{-1,0},{0,1},{1,0},{0,-1}}; private static boolean visited[][]; private static boolean inArea(int x, int y) { return x0 xm y0 yn; } public static void main(String[] args) { char[][] arr { {A,B,C,E}, {S,F,C,S}, {A,D,E,E}}; String s1 ABCCED; String s2 SEE; String s3 ABCB; System.out.println(exist(arr, s1)); System.out.println(exist(arr, s2)); System.out.println(exist(arr, s3)); } /** * 递归函数 * 从board[startx][starty]开始寻找word[index...word.size()] * param board * param word * param index * param startx * param starty * return */ private static boolean searchWord(char[][] board, String word, int index, int startx, int starty) { //判断字符串中最后一个元素是否在二维数组中 if(index word.length()-1) { return board[startx][starty] word.charAt(index); } if(board[startx][starty] word.charAt(index)) { visited[startx][starty] true; //从startx,starty出发向四个方向寻找 for(int i0;i4;i) { int newx startx d[i][0]; int newy starty d[i][1]; if(inArea(newx, newy) !visited[newx][newy] searchWord(board, word, index1, newx, newy)) { return true; } } visited[startx][starty] false; } return false; } public static boolean exist(char[][] board, String word) { m board.length; n board[0].length; visited new boolean [m][n]; for(int i0;im;i) { for(int j0;jn;j) { if(searchWord(board, word, 0, i, j)) { return true; } } } return false; } }程序输出结果如下truetruefalse