Blog of LCX

0%

LCR129

发表于 分类于 ， Valine：

问题描述

字母迷宫游戏初始界面记作 m x n 二维字符串数组 grid，请判断玩家是否能在 grid 中找到目标单词 target。
注意：寻找单词时 必须 按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用 。

img

示例 1：

1
2
输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCCED"
输出：true

示例 2：

1
2
输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "SEE"
输出：true

示例 3：

1
2
输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCB"
输出：false

提示：

  • m == grid.length
  • n = grid[i].length
  • 1 <= m, n <= 6
  • 1 <= target.length <= 15
  • grid 和 target 仅由大小写英文字母组成

解答

回溯，用visited数组记录是否走过，回溯之后把visited恢复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
  public boolean wordPuzzle(char[][] grid, String target) {
     int row = grid.length;
     int col = grid[0].length;
     boolean[][] visited = new boolean[grid.length][grid[0].length];
     for (int i = 0; i < row; i++) {
       for (int j = 0; j < col; j++) {
         boolean res = isexist(grid,target,visited,i,j);
         if(res) return true;
       }
     }
     return false;
  }

  public boolean isexist(char[][] grid, String target,boolean[][] visited,int i,int j) {
     if(grid[i][j] == target.charAt(0)) {
       if (target.length()==1) return true;
       visited[i][j] = true;
       if(i<grid.length-1 && visited[i+1][j]==false) {
         if(isexist(grid,target.substring(1),visited,i+1,j)) return true;
       }
       if(j<grid[0].length-1 && visited[i][j+1]==false) {
         if(isexist(grid, target.substring(1), visited, i, j + 1)) return true;
       }
       if(i>0 && visited[i-1][j]==false) {
         if(isexist(grid, target.substring(1), visited, i - 1, j)) return true;
       }
       if(j>0 && visited[i][j-1]==false) {
         if(isexist(grid, target.substring(1), visited, i, j - 1)) return true;
       }
       visited[i][j] = false;
     }
     return false;
  }
}