算法题（回溯）

一、题目1、括号生成LC 222、单词搜索LC 79二、题解1、括号生成LC 221分析采用回溯的思想解决。递归方法包括 left、right、ans、path、n 五个核心参数其中 left 与 right 分别记录已使用的左、右括号数量ans 用于存储所有合法的括号组合结果path 为固定长度的字符数组用于暂存单组括号组合n 为需要生成的括号对数。递归边界条件右括号使用次数达到 n此时左括号必然也使用了 n 次形成完整合法组合将 path 转换为字符串加入结果集后回溯至上一层。递归过程中当左括号使用次数小于 n 时可向 path 中添加左括号当右括号使用次数小于左括号时可添加右括号。一次递归结束也无需恢复现场因为下一次的获取的括号组合会覆盖上一次的组合。2解答class Solution { public ListString generateParenthesis(int n) { //初始化 ListString ans new ArrayList(); //结果列表存放最终结果 char[] path new char[2 * n]; //存放每一种括号组合 dfs(0, 0, ans, path, n); return ans; } //当前使用了left个左括号right个右括号 public void dfs(int left, int right, ListString ans, char[] path, int n){ if(right n){ //path已经放满获取了一种括号组合添加到结果列表中 ans.add(new String(path)); return; } if(left n){ path[left right] (; dfs(left 1, right, ans, path, n); } if(right left){ //左括号数要小于右括号数才可以选择 path[left right] ); dfs(left, right 1, ans, path, n); } } }2、单词搜索LC 791分析使用回溯方法解决。相较于基础回溯算法这题多了两个参数 i j 来表示搜索位置参数 k 表示字符的下标。通过两层循环遍历矩阵的每一个位置以每个位置作为起点启动深度优先搜索若某次搜索返回 true则证明矩阵中存在目标单词说明board数组中含有Word的字符组合直接返回最终结果。递归边界条件board数组当前位置的字符与word的对应字符不相等直接返回 false 终止当前分支如果相等且 k 值达到字符数组最大下标说明board数组中含有Word字符的组合返回true。对于遍历到的每个board数组中的位置将当前访问的矩阵位置置零作为访问标记在此次递归过程不能再继续访问四个方向递归完成后再恢复现场确保不影响下一次递归。2解答class Solution { static int[][] dir {{-1, 0},{1, 0},{0, -1},{0, 1}}; //方向上下左右 public boolean exist(char[][] board, String word) { //初始化 char[] wordChar word.toCharArray(); for(int i 0; i board.length; i){ //遍历board中每个元素 for(int j 0; j board[i].length; j){ if(dfs(i,j,0,board,wordChar)){ return true; } } } return false; } public boolean dfs(int i, int j, int k, char[][] board, char[] wordChar){ if(board[i][j] ! wordChar[k]){ //当前元素不符合对应字符 return false; } if(k wordChar.length -1){ //当前元素符合对应字符且为最大下标 return true; } board[i][j] 0; //标记当前元素为已使用的 for(int[] d : dir){ //向四个方向递归 int x i d[0]; int y j d[1]; if(x0 xboard.length y0 yboard[x].length dfs(x,y,k1,board,wordChar)){ return true; } } board[i][j] wordChar[k]; //恢复现场 return false; } }