当前位置：首页 > news >正文

LeetCode 解题思路 30（Hot 100）

news 2025/4/3 15:46:08

在这里插入图片描述

解题思路：

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

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

在这里插入图片描述

解题思路：

遍历起点： 从网格的每个单元格出发，尝试匹配单词的第一个字符。
递归搜索： 对当前单元格的四个相邻方向（上、下、左、右）进行递归搜索，确保字符匹配且未被访问过。
标记访问： 在搜索过程中临时标记已访问的单元格（如将字符改为特殊符号），并在回溯时恢复原状。
终止条件： 若完整匹配单词的所有字符，返回 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;}
}