递归函数中Python列表索引越界：有效括号校验报错求助

报错原因分析 #

你的代码触发索引越界的核心问题是空列表的处理不完整：

• 原代码里仅当lst1 == [] and cnt ==0时返回True，但当递归到空列表但cnt≠0（比如输入"(()"，最后递归到空时cnt=1），代码会继续执行后面的if lst1[0]判断，此时lst1是空列表，访问索引0必然触发list index out of range错误。
• 另外还有隐性问题：当cnt变成负数（比如输入")("，第一个字符是')'，cnt直接变为-1），此时已经可以确定括号无效，但你的代码仍会继续递归，做无意义的计算。

修正后的代码 #

def is_valid_paren(s, cnt=0):
    lst1 = list(s)
    # 空列表直接根据计数器判断是否有效
    if not lst1:
        return cnt == 0
    # 遇到右括号先检查是否有匹配的左括号
    if lst1[0] == ')':
        if cnt == 0:
            return False
        cnt -= 1
        return is_valid_paren(lst1[1:], cnt)
    elif lst1[0] == '(':
        cnt += 1
        return is_valid_paren(lst1[1:], cnt)
    else:
        # 非括号字符直接跳过递归
        return is_valid_paren(lst1[1:], cnt)

关键修改点 #

1. 完善空列表处理：只要列表为空，直接返回cnt == 0，既覆盖了有效情况，也彻底避免了空列表访问索引的错误。
2. 提前终止无效递归：遇到右括号时先判断cnt是否为0，若为0说明没有对应的左括号，直接返回False，不用继续递归。

内容的提问来源于stack exchange，提问作者apeman