22. 括号生成
22. 括号生成
题目：
题解：
class Solution { int left; //左括号 int right; //右括号 List<String> res; void dfs(int l, int r, StringBuilder sb) { if(l==0&&r==0) { res.add(sb.toString()); return ; } if(l>0) { sb.append('('); dfs(l-1, r, sb); sb.deleteCharAt(sb.length()-1); } //剩余的左括号也要少于右括号才能形成完整的括号 if(r>0&&l<r) { sb.append(')'); dfs(l, r-1, sb); sb.deleteCharAt(sb.length()-1); } } public List<String> generateParenthesis(int n) { left=n; right=n; res = new ArrayList<>(); dfs(left, right, new StringBuilder()); return res; } }79. 单词搜索
79. 单词搜索
题目：
题解：
class Solution { int n; int m; boolean[][] visited; boolean dfs(int x, int y, char[][] board, String word, int t) { // 先检查是否越界或已访问 if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y]) { return false; } // 检查当前字符是否匹配 if (board[x][y] != word.charAt(t)) { return false; } // 如果已经匹配到最后一个字符 if(t==word.length()-1) { return true; } visited[x][y]=true; // 向四个方向搜索（注意：题目只允许上下左右，不是8个方向！） boolean found = dfs(x + 1, y, board, word, t + 1) || dfs(x - 1, y, board, word, t + 1) || dfs(x, y + 1, board, word, t + 1) || dfs(x, y - 1, board, word, t + 1); //恢复现场 visited[x][y]=false; return found; } public boolean exist(char[][] board, String word) { n = board.length; m = board[0].length; visited = new boolean[n][m]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(board[i][j]==word.charAt(0)) { if(dfs(i, j, board, word, 0)) { return true; } } } } return false; } }
