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。