LeetCode 解题思路 30（Hot 100）

解题思路：

1. 递归参数： 生成括号的对数 n、结果集 result、当前路径 path、左括号数 open、右括号数 close。
2. 递归过程：

• 当当前路径 path 的长度等于 n * 2 时，说明已经生成有效括号，加入结果集。
• 若左括号数小于 n，将左括号加入临时字符串，递归处理字符串的下一个位置。
• 若右括号数小于左括号数，将右括号加入临时字符串，递归处理字符串的下一个位置。

Java代码：

class Solution {public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();backtrack(n, result, "", 0, 0);return result;}private void backtrack(int n, List<String> result, String path, int open, int close) {if (path.length() == n * 2) {result.add(path);return;}if (open < n) backtrack(n, result, path + "(", open + 1, close);if (close < open) backtrack(n, result, path + ")", open, close + 1);}
}

复杂度分析：

• 时间复杂度： O($4^n/\surd n$)。有效括号组合的数量遵循卡塔兰数，其渐近复杂度为 $4^n/\surd n$。每个组合需要 O(n) 时间构建，总时间复杂度为 O($4^n/\surd n$)。
• 空间复杂度： O(n)。递归调用栈的深度最大为 2n，但主要空间消耗来自结果存储，结果集大小为卡塔兰数，空间复杂度为 O($4^n/\surd n$)。算法本身的额外空间复杂度为 O(n)。

解题思路：

1. 遍历起点： 从网格的每个单元格出发，尝试匹配单词的第一个字符。
2. ​递归搜索： 对当前单元格的四个相邻方向（上、下、左、右）进行递归搜索，确保字符匹配且未被访问过。
3. ​标记访问： 在搜索过程中临时标记已访问的单元格（如将字符改为特殊符号），并在回溯时恢复原状。
4. 终止条件： 若完整匹配单词的所有字符，返回 true；若所有路径均失败，返回 false。

Java代码：

public class Solution {public boolean exist(char[][] board, String word) {int rows = board.length;int cols = board[0].length;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (dfs(board, word, i, j, 0)) {return true;}}}return false;}private boolean dfs(char[][] board, String word, int i, int j, int start) {if (i == -1 || i == board.length || j == -1 || j == board[0].length || board[i][j] != word.charAt(start)) {return false;}if (start == word.length() - 1) return true;char temp = board[i][j];board[i][j] = '#';boolean found = dfs(board, word, i + 1, j, start + 1)|| dfs(board, word, i - 1, j, start + 1)|| dfs(board, word, i, j + 1, start + 1)|| dfs(board, word, i, j - 1, start + 1);board[i][j] = temp;return found;}
}

复杂度分析：

• 时间复杂度： 最坏情况下为 O(M×N×4L)，M×N 是网格的总单元格数，每个单元格作为起点。4L 是每个起点的最长递归深度（单词长度为 L，每一步有4个方向选择）。
• 空间复杂度： O(L)，递归调用栈的深度最大为单词长度 L。