首页 > 代码库 > 79. Word Search

79. Word Search

2024-08-17 23:00:00   211人阅读

　　不定期更新leetcode解题java答案。

　　采用pick one的方式选择题目。

　　题意为给定二维字符数组，从中是否可以寻找到一条不重复经过同一位置的长链字符能够组成目标字符串。

　　例子如下：

　　Given board =

　　[
  　　[‘A‘,‘B‘,‘C‘,‘E‘],
  　　[‘S‘,‘F‘,‘C‘,‘S‘],
  　　[‘A‘,‘D‘,‘E‘,‘E‘]
　　]

　　word = "ABCCED", -> returns true,
　　word = "SEE", -> returns true,
　　word = "ABCB", -> returns false.

　　主要考察对数组操作的运用，采用迷路寻路回溯的方法进行处理。需要写一个功能函数用来判断是否该位置的字符满足所需求，此后进行上下左右的后一字符的递归检验，与此同时需要添加一个辅助的boolean二维数组判断该位置是否已经被走过。需要额外说的是，由于数组在递归的过程中值被改变则该数组即被改变（意思是再进行新的一次递归时，值也已经被改变了），在进行回溯处理时，需要额外将标记此位置是否已经被检测过的boolean二维数组进行修正。具体代码如下：

　

 1 public class Solution {
 2     public boolean exist(char[][] board, String word) {
 3         if(word.length() == 0)
 4             return true;
 5             
 6         boolean[][] map = new boolean[board.length][board[0].length];
 7         
 8         for(int i = 0; i < board.length; i++)
 9             for(int j = 0; j < board[0].length; j++)
10                 if(exist(board, word, 0, i, j, map))
11                     return true;
12                     
13         return false;
14     }
15     //location为检测字符串的位置，x和y分别是二维数组坐标，map为辅助boolean二维数组表示是否已经在此次检测中已经选中该字符
16     public boolean exist(char[][] board, String word, int location, int x, int y, boolean[][] map){
17         char tmpChar = word.charAt(location);
18         boolean result = false;
19         location++;
20         if(tmpChar != board[x][y])
21             return false;
22         else{
23             map[x][y] = true;
24             if(location == word.length())
25                 return true;
26             if(x > 0 && !map[x - 1][y])
27                 result = result || exist(board, word, location, x - 1, y, map);
28             if(x < board.length - 1 && !map[x + 1][y])
29                 result = result || exist(board, word, location, x + 1, y, map);
30             if(y > 0 && !map[x][y - 1])
31                 result = result || exist(board, word, location, x, y - 1, map);
32             if(y < board[0].length - 1 && !map[x][y + 1])
33                 result = result || exist(board, word, location, x, y + 1, map);
34             if(!result)
35                 map[x][y] = false;
36         }
37         return result;
38     }
39 }

 

79. Word Search


联系
我们