Leetcode第79题

题目描述

https://leetcode.cn/problems/word-search/

个人思路

我的想法很简单，就是用一个Boolean数组来标记元素是否被访问，对数组每个元素都执行一次搜索。在搜索过程中，先判断是否越界，然后依次判断上下左右是否存在目标字符。存在则继续调用搜索函数，直到全部发现返回true或者未发现返回false。需要注意的一点是，我们对访问后如果未命中，需要进行回溯，确保访问数组正确，以免刚开始向下访问时，还存在向上访问时的记录。

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

     boolean[][] n=new boolean[board.length][board[0].length];

     boolean flag;
     int temp=0;
     for (int i=0;i<board.length;i++){
         for (int j=0;j<board[0].length;j++){
             n=new boolean[board.length][board[0].length];
             if (board[i][j]==word.charAt(0)){
                 n[i][j]=true;
                 flag=find(i,j,board,word,1,n);

                 if(flag==true)return flag;
             }

         }
     }
     return false;
 }

 private boolean find(int i, int j, char[][] board, String word,int t,boolean[][] n) {
     if(t==word.length())return true;
     boolean flag;

     for (;t<word.length();t++){
         if ((i-1)>=0){
             if (board[i-1][j]==word.charAt(t) && n[i-1][j]==false){
                 n[i-1][j]=true;
                 flag=find(i-1,j,board,word,t+1,n);
                 if (flag==true)return flag;
                 n[i-1][j]=false;
             }

         }
         if((i+1)<= board.length-1){
             if (board[i+1][j]==word.charAt(t) && n[i+1][j]==false){
                 n[i+1][j]=true;
                 flag=find(i+1,j,board,word,t+1,n);
                 if (flag==true)return flag;
                 n[i+1][j]=false;
             }
         }
         if((j-1)>=0){
             if (board[i][j-1]==word.charAt(t) && n[i][j-1]==false){
                 n[i][j-1]=true;
                 flag=find(i,j-1,board,word,t+1,n);
                 if (flag==true)return flag;
                 n[i][j-1]=false;
             }
         }
        if((j+1)<=board[0].length-1){
            if (board[i][j+1]==word.charAt(t) && n[i][j+1]==false){
                n[i][j+1]=true;
                flag=find(i,j+1,board,word,t+1,n);
                if (flag==true)return flag;
                n[i][j+1]=false;
            }
        }

        return false;

     }
     return false;
 }

代码优化

针对上下左右我写了4个if，这样看着代码冗余，可以放在一起，并且对边界的判定情况可以放在搜索函数最前面（但这样会多执行一步）。

if(i<0 || j<0 || i>=m || j>=n || board[i][j]=='/0') return false; 

boolean ans = find(i-1,j,m,n,board,word,charindex+1)||search(i+1,j,m,n,board,word,charindex+1)||search(i,j-1,m,n,board,word,charindex+1)||search(i,j+1,m,n,board,word,charindex+1);

参考思路

无

收获

回溯+代码优化方式