p79

发表于 | 分类于 |

LeetCode p79 Word Search 题解

1.题目：

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 =

[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

题意：

输入一个字符串数组，和一个字符串，查找其中是否有某条路径可以连成这个字符串。

2.解题思路:

dfs

3.代码

[title] [] [url] [link text]
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
36
37
38
39
40
41
42
43
44
45
46
47
 
public class Solution {
    public int flag = 0;

	public boolean exist(char[][] board, String word) {

		if (word.equals(""))
			return true;
		if (board.length < 1 || board.length * board[0].length < word.length())
			return false;
		
		char[] c = word.toCharArray();
		int[][] mark = new int[board.length][board[0].length];
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {

				if (board[i][j] == c[0]) {
				    dfs(board, c, 0, i, j, mark);
				}
			}
		}
		return flag == 1 ? true : false;
	}

	public void dfs(char[][] board, char[] c, int a, int i, int j,
			int[][] mark) {
				if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1
				|| board[i][j] != c[a] || mark[i][j] == 1 || flag == 1)
			return;

		mark[i][j] = 1;
		if (c.length - 1 == a) {
			flag = 1;
			return;
		}

		// down
		dfs(board, c, a + 1, i + 1, j, mark);
		// up
		dfs(board, c, a + 1, i - 1, j, mark);
		// left
		dfs(board, c, a + 1, i, j + 1, mark);
		// right
		dfs(board, c, a + 1, i, j - 1, mark);
		mark[i][j] = 0;
	}
}

4.一些总结：