leetcode-单词探索

单词搜索

 

 

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

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

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

思路：回溯算法，返回false的条件是探索到达了边界，已经探索过了，探索的字母与给定字符串的字符不相等。 

探索是向上下左右探索，因此有四个回溯（bcakTrace()）。

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows=board.length; //长
        int cols=board[0].length;
        boolean res=false;
        boolean[][] mark=new boolean[rows][cols];
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(word.charAt(0)==board[i][j]){            //先找到字符串的起点
                    res=backTrace(0,word,board,i,j ,mark );
                    if(res==true)return true;
                }
            }
        }
        return false;
    }
  public boolean backTrace(int index,String word,char[][] board,int row,int col,boolean[][] mark){
      if(index==word.length())return true;          //回溯的边界条件
      if(row>=board.length||row<0||col>=board[0].length||col<0)return false;
      if(mark[row][col]==true||word.charAt(index)!=board[row][col])return false;
      mark[row][col]=true;
      if(backTrace(index+1,word,board,row+1,col,mark)||
        backTrace(index+1,word,board,row-1,col,mark)||
        backTrace(index+1,word,board,row,col+1,mark)||
        backTrace(index+1,word,board,row,col-1,mark))
          return true;
      mark[row][col]=false;                 //每次探索至边界，不成立时，都要将标记清除
      return false;
  }
    }