题目
单词搜索
给出一个二维的字母板和一个单词，寻找字母板网格中是否存在这个单词。
单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。每个单元中的字母最多只能使用一次。
样例
给出board =
[
"ABCE",
"SFCS",
"ADEE"
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
解题
直接深度搜索
public class Solution {
public boolean exist(char[][] board, String word) {
return method(board,word);
}
public boolean method(char[][] board,String word){
int row = board.length;
int col = board[0].length;
boolean[][] visited = new boolean[row][col];
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
if(dfs(board,visited,i,j,0,word))
return true;
return false;
}
public boolean dfs(char[][] board,boolean[][] visited,int row,int col,int index,String word){
if(word.length() == index){
return true;
}
if(row<0 || col<0||row>=board.length || col>=board[0].length) return false;
char ch = word.charAt(index);
if(!visited[row][col] && ch == board[row][col]){
visited[row][col] = true;
boolean res = dfs(board,visited,row-1,col,index+1,word)|| dfs(board,visited,row+1,col,index+1,word)
||dfs(board,visited,row,col-1,index+1,word)|| dfs(board,visited,row,col+1,index+1,word);
visited[row][col] = false;
return res;
}
return false;
}
}
Java Code
修改原始数组，降低空间复杂度
public class Solution {
/**
* @param board: A list of lists of character
* @param word: A string
* @return: A boolean
*/
public boolean exist(char[][] board, String word) {
// write your code here
return method(board,word);
}
public boolean method(char[][] board,String word){
int row = board.length;
int col = board[0].length;
for(int i=0;i<row;i++)
for(int j=0;j<col;j++){
if(dfs(board,i,j,0,word))
return true;
}
return false;
}
public boolean dfs(char[][] board,int row,int col,int index,String word){
if(word.length() == index){
return true;
}
if(row<0 || col<0||row>=board.length || col>=board[0].length) return false;
char ch = word.charAt(index);
if(board[row][col]!='+' && ch == board[row][col]){
char c = board[row][col];
board[row][col]='+';
boolean res = dfs(board,row-1,col,index+1,word)|| dfs(board,row+1,col,index+1,word)
||dfs(board,row,col-1,index+1,word)|| dfs(board,row,col+1,index+1,word);
board[row][col] = c;
return res;
}
return false;
}
}
Java Code
Python
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
for i in xrange(len(board)):
for j in xrange(len(board[0])):
if self.dfs(board,i,j,word,0):
return True
return False def dfs(self,board,row,col,word,index):
if index == len(word):
return True
if row<0 or col<0 or row>=len(board) or col>=len(board[0]):
return False
ch = word[index]
res = False
if(board[row][col]!='+' and board[row][col] ==ch):
c = board[row][col]
board[row][col] = '+'
res = self.dfs(board,row-1,col,word,index+1) or \
self.dfs(board,row,col-1,word,index+1) or \
self.dfs(board,row+1,col,word,index+1) or \
self.dfs(board,row,col+1,word,index+1)
if res:
return res
else:
board[row][col] = c
return False