查找单词-算法（深度优先）

题目

给定一个二维数组与一个单词，数组中每个元素为大写字母，判断单词是否出现在数组中。

如二维数组：

char[][] map = {
 {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};

目标单词：

ABCCEE

解题

深度优先，并且走过的标记一下

public class FindWordIn2DArrayTest {

  public static void main(String[] args) {
    char[][] map = {
  {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
    String target = "ABCCEE";

    System.out.println(isWordInMap(map, target));
  }

  private static boolean isWordInMap(char[][] map, String target) {
    for (int i = 0; i < map.length; i++) {
      for (int j = 0; j < map[i].length; j++) {
        if (dfs(map, i, j, target, 0)) {
          return true;
        }
      }
    }
    return false;
  }

  private static boolean dfs(char[][] map, int i, int j, String target, int k) {
    if (i < 0 || j < 0 || i >= map.length || j >= map[i].length || map[i][j] != target.charAt(k)) {
      return false;
    }
    if (k == target.length() - 1) {
      return true;
    }
    map[i][j] = '\0';
    boolean has = dfs(map, i + 1, j, target, k + 1)
        || dfs(map, i - 1, j, target, k + 1)
        || dfs(map, i, j + 1, target, k + 1)
        || dfs(map, i, j - 1, target, k + 1);
    return has;
  }
}