LeetCode-79-Word Search*

 

Word Search

 

 

 

来自 <https://leetcode.com/problems/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.

 

 

 

题目解读

 

给定一个2维字母面板和一个单词，查找该单词是否存在于此二维网格面板中。单词由二维邻接矩阵中的字母构成，同一个网格中的字母不能使用多于一次。

 

 

 

解析：这是一个深度优先搜索序列，其中有两个难点。

 

第一是判断深度优先搜索的终结条件，由于查找的是单词，可以使用单词的长度作为起终结条件。

 

第二由于同一个网格中的字母不能使用多于一次，所以要记录搜索路径。记录路径有两种方法，一种是使用一个专门的二维数组进行记录，另一种是采用将board中的字母替换成特殊字符。此代码中采用第二种方式。

 

 

 

Java代码:

 

public class Solution {
	
	public boolean exist(char[][] board, String word) {
		int rows = board.length; //行数
		int cols = board[0].length; //列数
		
		boolean result = false;
		for(int i=0; i<rows; i++) {
			for(int j=0; j<cols; j++) {
				if(searchLetter(board, word, i, j, 0)) {
					result = true;
				}
			}
		}
		return result;
	}
	
	private boolean searchLetter(char[][] board, String word, int currentRow, int currentCol, int currnetLetter) {
		// TODO Auto-generated method stub
		int rows = board.length;
		int cols = board[0].length;
		
		//判断是否越界
		if(currentRow<0 || currentRow>=rows || currentCol <0 || currentCol>= cols)
			return false;
		if(board[currentRow][currentCol] == word.charAt(currnetLetter)) {
			//记录board中当前元素的值
			char temp=board[currentRow][currentCol];
			board[currentRow][currentCol]='#';
			if(currnetLetter == word.length()-1) {
				return true;
			} else if(searchLetter(board, word, currentRow-1, currentCol, currnetLetter+1)
					||searchLetter(board, word, currentRow+1, currentCol, currnetLetter+1)
					||searchLetter(board, word, currentRow, currentCol-1, currnetLetter+1)
					||searchLetter(board, word, currentRow, currentCol+1, currnetLetter+1)){
				return true;
			}
			//如果查找失败，回复原来的元素
			board[currentRow][currentCol] = temp;
		} 
		return false;
	}

}

 算法性能：