[LeetCode] Word Search

图形化表述:

代码:

public class liubobo_8_4 {
/// 79. Word Search
/// Source : https://leetcode.com/problems/word-search/description/
///
/// 回溯法
/// 时间复杂度: O(m*n*m*n)
/// 空间复杂度: O(m*n)
private int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};//辅助数组，用于上下左右位移 ，这在二维数组中常常使用，简称偏移量
private int m, n;
private boolean[][] visited;//辅助数组，用于代表每个坐标是否被访问过

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

if(board == null || word == null)
throw new IllegalArgumentException("board or word can not be null!");

m = board.length;
if(m == 0)
throw new IllegalArgumentException("board can not be empty.");
n = board[0].length;
if(n == 0)
throw new IllegalArgumentException("board can not be empty.");

visited = new boolean[m][n];
for(int i = 0 ; i < m ; i ++)
for(int j = 0 ; j < n ; j ++)
if(searchWord(board, word, 0, i, j))
return true;

return false;
}

private boolean inArea( int x , int y ){
//inArea是辅助函数，用于分析坐标是否有效，分析有没有越界
return x >= 0 && x < m && y >= 0 && y < n;
}
// 核心递归函数
// 从board[startx][starty]开始, 寻找word[index...word.size())
private boolean searchWord(char[][] board, String word, int index,
int startx, int starty){

//assert(inArea(startx,starty));
if(index == word.length() - 1) {//终止条件
return board[startx][starty] == word.charAt(index);
}
if(board[startx][starty] == word.charAt(index)){
//找到了元素
visited[startx][starty] = true;
// 从startx, starty出发,向四个方向寻
for(int i = 0 ; i < 4 ; i ++){
int newx = startx + d[i][0];
int newy = starty + d[i][1];
//inArea是辅助函数，用于分析坐标是否有效
if(inArea(newx, newy) && !visited[newx][newy] &&
searchWord(board, word, index + 1, newx, newy))
return true;
}
//寻找没找到，就放弃占用这个位置
visited[startx][starty] = false;
}
return false;
}

public static void main(String args[]){

char[][] b1 = { {'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}};

String words[] = {"ABCCED", "SEE", "ABCB" };
for(int i = 0 ; i < words.length ; i ++)
if((new liubobo_8_4()).exist(b1, words[i]))
System.out.println("found " + words[i]);
else
System.out.println("can not found " + words[i]);

// ---

char[][] b2 = {{'A'}};
if((new liubobo_8_4()).exist(b2,"AB"))
System.out.println("found AB");
else
System.out.println("can not found AB");

}
}