LeetCode(079)-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.

Example:

board = [ [‘A’,‘B’,‘C’,‘E’], [‘S’,‘F’,‘C’,‘S’], [‘A’,‘D’,‘E’,‘E’] ]

Given word = “ABCCED”, return true. Given word = “SEE”, return true. Given word = “ABCB”, return false.

翻译：

给定一个2D板和一个单词，找出这个单词是否存在于网格中。 单词可以由顺序相邻的单元格组成，其中“相邻”单元格是水平或垂直相邻的单元格。同一信元不可使用超过一次。 例子: 董事会= ( [A, B, C,“E”), [’ S ', ’ F ', ’ C ', ’ S ‘], [’ A ', ’ D ', ’ E ', ’ E '] ] 给定word = “ABCCED”，返回true。 给定word = “SEE”，返回true。 给定word = “ABCB”，返回false。

思路：

我们采用回溯法处理此问题。 我们首先分析问题，如何去找匹配的字符串，第一步先是从数组中找到匹配word第一个字符的位置，接下来就只能在这个位置的上下左右四个方向进行递归搜索，看是否有匹配word的字符串，如果这些位置中的字母和word下一个字母相等，则从这个位置继续搜索。我们每次从一个元素出发时，对board中元素已访问的标志可以设置一个访问标志数组，也可以把已访问的元素设置为某个特殊字符 ，如果搜索失败，我们需要恢复标志数组对应的坐标，虽然单次搜索字符不能重复，但是每次从一个新的元素触发，这个字符还是可以使用的。

代码实现：

class Solution { public static boolean[][] bl; public boolean search(char[][] board,int i,int j,String word,int index){ //找到和word完全匹配的路线 if(index==word.length()) return true; //对角标进行合法性检查 if(i<0 || i>=board.length || j<0 || j>=board[i].length || //当前坐标是否是字符串需要匹配的字符 board[i][j]!=word.charAt(index) || //当前坐标字符是否被使用 bl[i][j]) return false; //当前坐标可用，将其占用 bl[i][j]=true; //左边搜素 if(search(board, i-1, j, word, index+1)|| //右边搜索 search(board, i+1, j, word, index+1)|| //下边搜索 search(board, i, j-1, word, index+1)|| //上面搜索 search(board, i, j+1, word, index+1)){ return true; } //以此坐标搜素完毕后并未找到对应字符串，将次坐标设置为可用。 bl[i][j]=false; return false; } public boolean exist(char[][] board, String word) { bl=new boolean[board.length][board[0].length]; for(int i=0 ; i<board.length ; i++){ for(int j=0 ; j<board[0].length ; j++){ //找到二维数组中和word首字母匹配的坐标，并通过此坐标进行搜索。 if(board[i][j]==word.charAt(0)&&search(board,i,j,word,0)) return true; } } return false; } }