数据结构Python版练习题（二）

 解题代码：

def count(s):
    if (s == "()"):
        return 1
    else:
        left = 0
        right = 0
        i = 0
        while i < len(s):
            if s[i] == '(':
                left += 1
            if s[i] == ')':
                right += 1
            if (left == right):
                if (i == len(s) - 1):
                    s = s[1:len(s) - 1]
                    sum = 2 * count(s)
                    return sum
                else:
                    sum = count(s[0:i + 1]) + count(s[i + 1:len(s)])
                    return sum
            i += 1

s = input()
print(count(s))

 解题思路分析：

本题采用的是一种递归的解题方法。

递归的终止条件是（），此时返回值1.

如果不满足终止条件，则采用以下步骤：

1. 初始化两个变量，left表示左括号个数，right表示右括号个数。
2. 从头开始遍历，遇到一个左括号‘（’则left加一，遇到一个右括号‘）’right加一。
3. 如果left等于right，则说明这时候已经完成了匹配，但是如果输入类似于“（（））（（（）））”，则此时只匹配了前四个“（（））”，这时候就需要将原输入分为两个部分“（（））”以及“（（（）））”。函数的返回值就是这两部分分别递归调用函数得到的返回值之和。如果输入类似于“（（（））（））”；left等于right时，这时候匹配完了整个输入，这时候就需要将“（（（））（））”拆去最外面的左括号和右括号，得到“（（））（）”，之后函数的返回值就等于两倍的“（（））（）”递归调用函数得到的返回值。
4. 到达终止条件之后，就会得到输出。

复杂度分析：

假设输入长度为n，如程序所示：
while i < len(s):
    if s[i] == '(':
        left += 1
    if s[i] == ')':
        right += 1
    if (left == right):
        if (i == len(s) - 1):
            s = s[1:len(s) - 1]
            sum = 2 * count(s)
            return sum
        else:
            sum = count(s[0:i + 1]) + count(s[i + 1:len(s)])
            return sum
    i += 1
这一段包含一个一个循环，循环中有递归，则时间复杂度近似于O(n2)
易得空间复杂度为O(n)。

验证：