欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 79

程序员文章站 2022-06-07 10:12:22
...
class Solution {
    public boolean exist(char[][] board, String word) {
        int hang = board.length;
        int lie = board[0].length;
        int sum = 0;//记录有没有word存在,也可以记录存在的个数
        //设置一个边界矩阵,也可以保证相同的字母单元格不得使用两次
        int [][]bianjie =new int [hang+2][lie+2];
        //给第一列和最后一列赋值1
        for(int i = 0 ;i<hang+2;i++){
            bianjie[i][0] = bianjie[i][lie+1] = 1;
        }
        //给第一行和最后一行赋值1
        for(int i = 0;i<lie+2;i++){
            bianjie[0][i] = bianjie[hang+1][i] = 1;
        }
        
        for(int i = 0 ; i<hang;i++){
            for(int j = 0;j<lie;j++){
                if(board[i][j]==word.charAt(0) && bianjie[i+1][j+1]==0){
                    bianjie[i+1][j+1]=1;
                    sum += exist1(board , i , j , word, 0,bianjie);
                    bianjie[i+1][j+1]=0;
                }
            }
        }
        if(sum>0){
            return true;
        } 
        else return false;
    }
    
    public int exist1(char[][] board , int i_temp, int j_temp ,String word, int k_word,int [][]bianjie){
        int len_word = word.length();
        if((k_word+1) == len_word){
            return 1;
        }
        int sum  = 0;
        int i_bianjie = i_temp+1;
        int j_bianjie = j_temp+1;
        //上
        if(bianjie[i_bianjie-1][j_bianjie]==0 && board[i_temp-1][j_temp]==word.charAt(k_word+1)){
            bianjie[i_bianjie-1][j_bianjie]=1;
            sum += exist1(board , i_temp-1, j_temp , word, k_word+1,bianjie);
            bianjie[i_bianjie-1][j_bianjie]=0;
        }
        //下
        if(bianjie[i_bianjie+1][j_bianjie]==0 && board[i_temp+1][j_temp]==word.charAt(k_word+1)){
            bianjie[i_bianjie+1][j_bianjie]=1;
            sum += exist1(board , i_temp+1, j_temp , word, k_word+1,bianjie);
            bianjie[i_bianjie+1][j_bianjie]=0;
        }
        //左
        if(bianjie[i_bianjie][j_bianjie-1]==0 && board[i_temp][j_temp-1]==word.charAt(k_word+1)){
            bianjie[i_bianjie][j_bianjie-1]=1;
            sum += exist1(board , i_temp, j_temp-1 , word, k_word+1,bianjie);
            bianjie[i_bianjie][j_bianjie-1]=0;
        }
        //右
        if(bianjie[i_bianjie][j_bianjie+1]==0 && board[i_temp][j_temp+1]==word.charAt(k_word+1)){
            bianjie[i_bianjie][j_bianjie+1]=1;
            sum += exist1(board , i_temp, j_temp+1 , word, k_word+1,bianjie);
            bianjie[i_bianjie][j_bianjie+1]=0;
        }
        
        return sum;
    }
    
    
}

思路:每一次先判断本步是否已经走完,可以返回;

再走的时候,下一步 可以走再走

 

没过:超时;

LeetCode 79

一点点优化:

class Solution {
    public boolean exist(char[][] board, String word) {
        int hang = board.length;
        int lie = board[0].length;
        boolean res = false;//记录有没有word存在,也可以记录存在的个数
        //设置一个边界矩阵,也可以保证相同的字母单元格不得使用两次
        boolean [][]bianjie =new boolean [hang+2][lie+2];
        //给第一列和最后一列赋值1
        for(int i = 0 ;i<hang+2;i++){
            bianjie[i][0] = bianjie[i][lie+1] = true;
        }
        //给第一行和最后一行赋值1
        for(int i = 0;i<lie+2;i++){
            bianjie[0][i] = bianjie[hang+1][i] = true;
        }
        
        for(int i = 0 ; i<hang;i++){
            for(int j = 0;j<lie;j++){
                if(board[i][j]==word.charAt(0) && bianjie[i+1][j+1]==false){
                    bianjie[i+1][j+1]=true;
                    res = exist1(board , i , j , word, 0,bianjie);
                    if(res) return res;
                    bianjie[i+1][j+1]=false;
                }
            }
        }
        return res;
    }
    
    public boolean exist1(char[][] board , int i_temp, int j_temp ,String word, int k_word,boolean [][]bianjie){
        int len_word = word.length();
        if((k_word+1) == len_word){
            return true;
        }
        boolean res = false;
        int i_bianjie = i_temp+1;
        int j_bianjie = j_temp+1;
        //上
        if(bianjie[i_bianjie-1][j_bianjie]==false && board[i_temp-1][j_temp]==word.charAt(k_word+1)){
            bianjie[i_bianjie-1][j_bianjie]=true;
            res = exist1(board , i_temp-1, j_temp , word, k_word+1,bianjie);
            if(res) return true;//剪枝,很关键的一步
            bianjie[i_bianjie-1][j_bianjie]=false;
        }
        //下
        if(bianjie[i_bianjie+1][j_bianjie]==false && board[i_temp+1][j_temp]==word.charAt(k_word+1)){
            bianjie[i_bianjie+1][j_bianjie]=true;
            res = exist1(board , i_temp+1, j_temp , word, k_word+1,bianjie);
            if(res) return true;
            bianjie[i_bianjie+1][j_bianjie]=false;
        }
        //左
        if(bianjie[i_bianjie][j_bianjie-1]==false && board[i_temp][j_temp-1]==word.charAt(k_word+1)){
            bianjie[i_bianjie][j_bianjie-1]=true;
            res = exist1(board , i_temp, j_temp-1 , word, k_word+1,bianjie);
            if(res) return true;
            bianjie[i_bianjie][j_bianjie-1]=false;
        }
        //右
        if(bianjie[i_bianjie][j_bianjie+1]==false && board[i_temp][j_temp+1]==word.charAt(k_word+1)){
            bianjie[i_bianjie][j_bianjie+1]=true;
            res = exist1(board , i_temp, j_temp+1 , word, k_word+1,bianjie);
            if(res) return true;
            bianjie[i_bianjie][j_bianjie+1]=false;
        }
        
        
        return false;
    }
    
    
}

加入了减枝,通过

LeetCode 79