自己怎么做淘宝客网站吗,天水做网站的公司,海外网站建设推广,ps软件下载免费版解题思路#xff1a;
递归参数#xff1a; 生成括号的对数 n、结果集 result、当前路径 path、左括号数 open、右括号数 close。递归过程#xff1a;
当当前路径 path 的长度等于 n * 2 时#xff0c;说明已经生成有效括号#xff0c;加入结果集。若左括号数小于 n…
解题思路
递归参数 生成括号的对数 n、结果集 result、当前路径 path、左括号数 open、右括号数 close。递归过程
当当前路径 path 的长度等于 n * 2 时说明已经生成有效括号加入结果集。若左括号数小于 n将左括号加入临时字符串递归处理字符串的下一个位置。若右括号数小于左括号数将右括号加入临时字符串递归处理字符串的下一个位置。
Java代码
class Solution {public ListString generateParenthesis(int n) {ListString result new ArrayList();backtrack(n, result, , 0, 0);return result;}private void backtrack(int n, ListString 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 / √ n 4ⁿ/√n 4n/√n)。有效括号组合的数量遵循卡塔兰数其渐近复杂度为 4 n / √ n 4ⁿ/√n 4n/√n。每个组合需要 O(n) 时间构建总时间复杂度为 O( 4 n / √ n 4ⁿ/√n 4n/√n)。空间复杂度 O(n)。递归调用栈的深度最大为 2n但主要空间消耗来自结果存储结果集大小为卡塔兰数空间复杂度为 O( 4 n / √ n 4ⁿ/√n 4n/√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 index) {if (i -1 || i board.length || j -1 || j board[0].length || board[i][j] ! word.charAt(index)) {return false;}if (index word.length() - 1) return true;char temp board[i][j];board[i][j] #;boolean found dfs(board, word, i 1, j, index 1)|| dfs(board, word, i - 1, j, index 1)|| dfs(board, word, i, j 1, index 1)|| dfs(board, word, i, j - 1, index 1);board[i][j] temp;return found;}
}复杂度分析
时间复杂度 最坏情况下为 O(M×N×4L)M×N 是网格的总单元格数每个单元格作为起点。4L 是每个起点的最长递归深度单词长度为 L每一步有4个方向选择。空间复杂度 O(L)递归调用栈的深度最大为单词长度 L。
