[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”); }}

尝到你和你在一起的快乐，你是唯一能让我尝到酸甜苦辣的人。