计算字符串中的合法括号序列数量 - Python 递归算法

使用递归的方法解决这个问题。\n\n算法步骤如下：\n\n1. 定义一个变量count，用于记录合法的括号序列数量。\n2. 从字符串的第一个字符开始，遍历每个字符：\n - 如果字符是'('，将其加入一个堆栈中。\n - 如果字符是')'，检查堆栈是否为空，如果不为空，则弹出堆栈顶部的'('字符，count加1。\n - 如果字符是'?'，则有两种选择，可以将其替换为'('或者')'：\n - 将'('加入堆栈中，然后递归处理剩余的字符串。\n - 如果堆栈不为空，将堆栈顶部的'('字符弹出，然后递归处理剩余的字符串。\n3. 返回count作为结果。\n\n下面是使用Python实现的代码：\n\npython\ndef countValidParentheses(s):\n def helper(s, index, stack, count):\n if index == len(s):\n if len(stack) == 0:\n count += 1\n return count\n \n if s[index] == '(':\n stack.append('(')\n elif s[index] == ')':\n if len(stack) > 0:\n stack.pop()\n count += 1\n elif s[index] == '?':\n stack.append('(')\n count = helper(s, index + 1, stack, count)\n stack.pop()\n \n if len(stack) > 0:\n stack.pop()\n count = helper(s, index + 1, stack, count)\n stack.append('(')\n \n return count\n \n return helper(s, 0, [], 0)\n\n\n使用示例：\n\npython\ns = "((?))??"\ncount = countValidParentheses(s)\nprint(count) # 输出4\n\n\n在上述示例中，字符串"((?))??"可以组成以下4种合法的括号序列："((()))", "(()())", "(())()", "()()()"\n\n时间复杂度分析：假设字符串的长度为n，对于每个字符，我们有两种选择，所以时间复杂度为O(2^n)。