力扣-Hot100-回溯【算法学习day.39】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

---

习题

1.括号生成

题目链接:22. 括号生成 - 力扣（LeetCode）

题面:

基本分析: 这道题很经典的回溯题，通过观察我们可以发现，从左往右数，左括号的数量都大于或者等于右括号的数量，于是我们就可以定义一个递归函数，来执行此过程，当剩下的右括号数量为0时，就表示递归结束了

代码:

class Solution {List<String> ans = new ArrayList<>();int n;public List<String> generateParenthesis(int n) {this.n = n;recursion(n,n,"");return ans;}public void recursion(int lastleft,int lastright,String pre){if(lastright==0){ans.add(pre);}if(lastleft>0){recursion(lastleft-1,lastright,pre+"(");}if(lastright>lastleft){recursion(lastleft,lastright-1,pre+")");}}
}

---

2.单词搜索

题目链接:79. 单词搜索 - 力扣（LeetCode）

题面:

分析:在主函数中，我们遍历这个二维数组，如果存在字符与单词的首字符相等，那我们就进入定义好的递归函数，并给这个首字符的位置打上标记，避免重复读取，自定义递归函数recursion，有三个参数，分别是x，y，count，分别表示上一个读取点的横纵坐标，和这次应该匹配word的第几个字符，我们以上一次的x，y作为出发点，分别判断上下左右的字符是否等于words[count]，如果不等，就返回false，如果相等，就进入下一层递归，在此之前需要将点打上标记，出递归也别忘了将标记删除，递归结束的条件就是count等于word的长度

代码:

class Solution {int n;int m;int[][] flag;char[][] board;char[] wrods;int wlen;public boolean exist(char[][] board, String word) {this.board = board;wrods = word.toCharArray();wlen = wrods.length; n = board.length;m = board[0].length;flag = new int[n][m];for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(board[i][j]==wrods[0]){flag[i][j]=1;boolean isTrue = recursion(i,j,1);flag[i][j] = 0;if(isTrue)return true;}}}return false;}public boolean recursion(int x,int y,int count){if(count==wlen){return true;}boolean ans = false;if(x-1>=0&&board[x-1][y]==wrods[count]&&flag[x-1][y]!=1){flag[x-1][y] = 1;ans =  recursion(x-1,y,count+1)||ans;flag[x-1][y] = 0;}if(x+1<n&&board[x+1][y]==wrods[count]&&flag[x+1][y]!=1){flag[x+1][y] = 1;ans =  recursion(x+1,y,count+1)||ans;flag[x+1][y] = 0;}if(y-1>=0&&board[x][y-1]==wrods[count]&&flag[x][y-1]!=1){flag[x][y-1] = 1;ans =  recursion(x,y-1,count+1)||ans;flag[x][y-1] = 0;}if(y+1<m&&board[x][y+1]==wrods[count]&&flag[x][y+1]!=1){flag[x][y+1] = 1;ans =  recursion(x,y+1,count+1)||ans;flag[x][y+1] = 0;}return false||ans;}
}

---

后言

上面是力扣Hot100的回溯专题，下一篇是其他专题的习题，希望有所帮助，一同进步，共勉！