[leetcode]Word Search

第二遍的做法居然跟第一遍完全一样：

新博文地址：[leetcode]Word Search

Word Search

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.

好多天没刷题了，手都生了。。。

迷宫问题是回溯算法的典型应用，这道题就是典型的回溯算法，比较烦人的一点是不许走回头路，一种方法是将走过的节点做出标记（不需要改变原矩阵）；另一种做法就是走过的节点就删掉（需要改变原矩阵），这样就不会走回头路了。我采取的是后一种。

顺序扫描board矩阵，遇到跟word第一个字母相同的节点就开始上下左右搜索，以SEE为例：

 

遇到第一个S，board[1][0]，将该S删掉，以防走回头路，然后继续dfs，发现无论怎么走都不满足条件，ok，说明此路不通，将方才删掉的S重新加上去。

 

遇到第二个S，board[1][3]，dfs之，发现可以向上走，找到E，board[0][3]，然后此路不通了，将删掉的E添加上，并重新回溯到S，发现下面还有路可能走的通，找到E之后发现还可以向左走，然后就木有然后了。

public boolean exist(char[][] board, String word) {
		int height = board.length;
		int length = board[0].length;
		if (height * length < word.length()) {
			return false;
		}

		for (int row = 0; row < height; row++) {
			for (int column = 0; column < length; column++) {
				if (board[row][column] == word.charAt(0)) {
	    			   if( dfs(board, word.substring(1), row, column)) return true;
				}
			}
		}
		return false;
	}
	private boolean dfs(char[][] board, String word, int row, int column) {
		if (word.length() == 0) {
			return true;
		}
		int height = board.length;
		int length = board[0].length;
		char tem = board[row][column];
		board[row][column] = '~';//用~标记删除，很冒险，因为题中并未说字符串不包含~
		if (row < height - 1&& board[row + 1][column] == word.charAt(0)) {//down
			if(dfs(board, word.substring(1), row + 1, column)) return true;
		} //第一次做，全部用的else if，这是不对的，因为向下不通还需要向下找
		if (column < length - 1&&board[row][column + 1] == word.charAt(0)){//right
			if(dfs(board, word.substring(1), row, 1 + column)) return true;
		} //但是向某一个方向已经走通了，就不需要再迭代了，除非题中要求求出全部路径
		if (row > 0 && board[row - 1][column] == word.charAt(0)) {// get up
			if(dfs(board, word.substring(1), row - 1, column)) return true;
		} 
		if (column > 0 && board[row][column - 1] == word.charAt(0)) {// get left
			if(dfs(board, word.substring(1), row, column - 1)) return true;
		}//如果上下左右都走不通，那就说这个节点是不通的，将删掉的字母添加进去，回溯
		board[row][column] = tem;
		return false;
	}