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;
}
}
思路:每一次先判断本步是否已经走完,可以返回;
再走的时候,下一步 可以走再走
没过:超时;
一点点优化:
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;
}
}
加入了减枝,通过
下一篇: ElementUI中日期选择器级联