首页 > 代码库 > Word Search leetcode java
Word Search leetcode java
题目:
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[ ["ABCE"], ["SFCS"], ["ADEE"]]word =
"ABCCED"
, -> returns true
,word =
"SEE"
, -> returns true
,word = "ABCB"
, -> returns false
.
题解:
这道题分析看,就是一个词,在一行出现也是true,一列出现也是true,一行往下拐弯也是true,一行往上拐弯也是true,一列往左拐弯也是true,一列往右拐弯也是true。所以是要考虑到所有可能性,基本思路是使用DFS来对一个起点字母上下左右搜索,看是不是含有给定的Word。还要维护一个visited数组,表示从当前这个元素是否已经被访问过了,过了这一轮visited要回false,因为对于下一个元素,当前这个元素也应该是可以被访问的。
代码如下:
1 public boolean exist(char[][] board, String word) {
2 int m = board.length;
3 int n = board[0].length;
4 boolean[][] visited = new boolean[m][n];
5 for (int i = 0; i < m; i++) {
6 for (int j = 0; j < n; j++) {
7 if (dfs(board, word, 0, i, j, visited))
8 return true;
9 }
10 }
11 return false;
12 }
13
14 public boolean dfs(char[][] board, String word, int index, int rowindex, int colindex, boolean[][] visited) {
15 if (index == word.length())
16 return true;
17 if (rowindex < 0 || colindex < 0 || rowindex >=board.length || colindex >= board[0].length)
18 return false;
19 if (visited[rowindex][colindex])
20 return false;
21 if (board[rowindex][colindex] != word.charAt(index))
22 return false;
23 visited[rowindex][colindex] = true;
24 boolean res = dfs(board, word, index + 1, rowindex - 1, colindex,
25 visited)
26 || dfs(board, word, index + 1, rowindex + 1, colindex, visited)
27 || dfs(board, word, index + 1, rowindex, colindex + 1, visited)
28 || dfs(board, word, index + 1, rowindex, colindex - 1, visited);
29 visited[rowindex][colindex] = false;
30 return res;
31 }
2 int m = board.length;
3 int n = board[0].length;
4 boolean[][] visited = new boolean[m][n];
5 for (int i = 0; i < m; i++) {
6 for (int j = 0; j < n; j++) {
7 if (dfs(board, word, 0, i, j, visited))
8 return true;
9 }
10 }
11 return false;
12 }
13
14 public boolean dfs(char[][] board, String word, int index, int rowindex, int colindex, boolean[][] visited) {
15 if (index == word.length())
16 return true;
17 if (rowindex < 0 || colindex < 0 || rowindex >=board.length || colindex >= board[0].length)
18 return false;
19 if (visited[rowindex][colindex])
20 return false;
21 if (board[rowindex][colindex] != word.charAt(index))
22 return false;
23 visited[rowindex][colindex] = true;
24 boolean res = dfs(board, word, index + 1, rowindex - 1, colindex,
25 visited)
26 || dfs(board, word, index + 1, rowindex + 1, colindex, visited)
27 || dfs(board, word, index + 1, rowindex, colindex + 1, visited)
28 || dfs(board, word, index + 1, rowindex, colindex - 1, visited);
29 visited[rowindex][colindex] = false;
30 return res;
31 }
Reference:http://blog.csdn.net/yiding_he/article/details/18893621
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。