题目：
给定一个二维平面的字母和一个单词，看是否可以在这个二维平面上找到该单词。其中找到这个单词的规则是，从一个字母出发，可以横向或者纵向连接二维平面上的其他字母。同一个位置的字母只能使用一次。
输入：
（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 x>=0 && x<m && y>=0 && y<n; } 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 i=0;i<4;i++) { int newx = startx + d[i][0]; int newy = starty + d[i][1]; if(inArea(newx, newy) && !visited[newx][newy] && searchWord(board, word, index+1, 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 i=0;i<m;i++) { for(int j=0;j<n;j++) { if(searchWord(board, word, 0, i, j)) { return true; } } } return false; } }程序输出结果如下：
true
true
false
