数据结构与算法自学笔记（16）- 嵌套类问题的递归解题套路

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是讲解039的内容，总结了嵌套类问题的递归解题套路。这类问题的共同特点是存在嵌套结构（如括号嵌套），需要用递归来处理。

前置知识

在学习嵌套类问题之前，需要掌握以下基础知识：

• 讲解017、020、021、023、036、037、038
• 这些章节都分析过递归，尤其是讲解038，不熟悉的同学可以先熟悉一下

---

039【必备】嵌套类问题的递归解题套路

核心解题思路

基本套路模板

嵌套类问题的解题套路可以概括为：

1. 定义全局变量 where：记录当前解析到的位置
2. 递归函数 f(i)：从位置i开始解析，遇到字符串终止或嵌套条件终止就返回
3. 返回值机制：f(i)负责这一段的结果，返回前更新全局变量where
4. 位置传递：让上级函数通过where知道解析到了什么位置，进而继续

执行细节

• 如果f(i)遇到嵌套条件开始，就调用下级递归去处理嵌套
• 下级会负责嵌套部分的计算结果
• f(i)下级处理完成后，可以根据下级更新的全局变量where，知道该从什么位置继续解析

---

题目一：含有嵌套的表达式求值

问题描述

请写一个整数计算器，支持加减乘三种运算和括号。

• 数据范围：0 < |s| < 100，保证计算结果始终在整型范围内
• 要求：空间复杂度 O(n)，时间复杂度 O(n)

测试链接：

• LeetCode：https://leetcode.cn/problems/basic-calculator-iii/
• 牛客网：https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4

核心思想

使用递归处理括号嵌套，同时用两个列表分别存储数字和操作符。通过push辅助函数处理运算优先级：

• 乘除法优先级高：遇到时立即计算，并更新数字列表的最后一个数
• 加减法优先级低：先将数字和操作符存入列表
• 遇到左括号(：递归调用自身 _f 来计算括号内的值，把它当作一个整体的数字
• 遇到右括号 ) 或字符串末尾：结束当前层级的计算,并对 numbers 和 ops 列表中的加减法进行最终求和

算法实现

class Solution:
    def calculate(self, s: str) -> int:
        """
        主函数，初始化共享索引并启动递归
        """
        self.where = 0
        return self._f(list(s), 0)

    # s[i....]开始计算，遇到字符串终止 或者 遇到)停止
    # 返回 : 自己负责的这一段，计算的结果
    # 返回之间，更新全局变量where，为了上游函数知道从哪继续！
    def _f(self, s: List[str], i: int) -> int:
        """
        递归函数，处理一个括号内的或整个表达式的求值
        """
        cur = 0
        numbers = []
        ops = []
        
        while i < len(s) and s[i] != ')': # 未终止且未遇到右括号
            if s[i].isdigit(): # 是数字
                cur = cur * 10 + int(s[i])
                i += 1
            elif s[i] != '(': # 不是左括号
                # 遇到了运算符 + - * /
                self._push(numbers, ops, cur, s[i])
                i += 1
                cur = 0
            else: # 是左括号
                # i (.....)
                # 遇到了左括号！
                # 递归调用 f，计算括号内的结果
                cur = self._f(s, i + 1)
                # 递归返回后，where 指向了 ')' 的位置，i 需要跳到 ')' 之后
                i = self.where + 1
        
        # 如果碰到了右括号，将最后一个数字（或括号运算结果）加入列表，并更新全局索引
        self._push(numbers, ops, cur, '+') # 末尾添加一个 '+' 不影响最终计算
        # 更新全局索引，让上级函数知道从哪继续
        self.where = i
        return self._compute(numbers, ops)

    def _push(self, numbers: List[int], ops: List[str], cur: int, op: str):
        """辅助函数，处理数字和操作符的入栈逻辑，并处理乘除法"""
        if not numbers or ops[-1] == '+' or ops[-1] == '-':
            # 如果是第一个数，或者前一个运算符是+或-，直接入栈
            numbers.append(cur)
            ops.append(op)
        else:
            # 如果前一个运算符是*或/，立即计算
            top_number = numbers[-1]
            top_op = ops[-1]
            if top_op == '*':
                numbers[-1] = top_number * cur
            else: # top_op == '/'
                # Python 的 // 是向下取整，题目要求向零取整
                numbers[-1] = int(top_number / cur)
            ops[-1] = op # 更新操作符

            # 具体例子   
            # 原始：3 * 4 + 5
            #     处理到 * 4 时：
            #     - numbers: [3, 4] → [12] (3*4=12)
            #     - ops: ['*'] → ['+'] (更新操作符)  
            # 这样下一个数字 5 就能正确地与 12 进行加法运算

    def _compute(self, numbers: List[int], ops: List[str]) -> int:
        """辅助函数，计算只有加减法的最终结果"""
        ans = numbers[0]
        for i in range(1, len(numbers)):
            ans += numbers[i] if ops[i - 1] == '+' else -numbers[i]
        return ans

算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 核心技巧：递归处理嵌套 + 分离处理优先级

---

题目二：含有嵌套的字符串解码

问题描述

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。

示例：输入：s = "3[a2[c]]"，输出："accaccacc"

测试链接：https://leetcode.cn/problems/decode-string/

核心思想

递归解码嵌套字符串。有嵌套就一定有数字：

• 遇到字母：直接拼接到当前层级的结果 path 中
• 遇到数字：累加成一个完整的数字 cnt，这代表后续 [] 内字符串的重复次数
• 遇到左括号[：说明进入了一个新的嵌套层级。此时，递归调用 _f 来解码 [] 内的子问题。递归返回后，将得到的子字符串重复 cnt 次，拼接到 path 中。
• 遇到右括号 ] 或字符串末尾：当前层级解码结束，返回 path。

算法实现

class Solution:
    def decodeString(self, s: str) -> str:
        """
        主函数，初始化共享索引并启动递归
        """
        self.where = 0
        return self._f(list(s), 0)

    # s[i....]开始计算，遇到字符串终止 或者 遇到 ] 停止
    # 返回 : 自己负责的这一段字符串的结果
    # 返回之间，更新全局变量where，为了上游函数知道从哪继续！
    def _f(self, s: list, i: int) -> str:
        """
        递归函数，解码一个层级的字符串
        """
        path = []
        cnt = 0
        while i < len(s) and s[i] != ']':
            if 'a' <= s[i] <= 'z' or 'A' <= s[i] <= 'Z':  # 比较范围
                path.append(s[i])
                i += 1
            elif s[i].isdigit():
                cnt = cnt * 10 + int(s[i])
                i += 1
            else:
                # 遇到 [ 
                # 递归调用 f 来解码括号内的内容
                inner_str = self._f(s, i + 1)
                # 将解码后的子串重复 cnt 次
                path.append(cnt * inner_str)
                # 更新 i 到 ']' 之后的位置
                i = self.where + 1
                # 重置 cnt
                cnt = 0
        
        # 更新全局索引，以便上层函数知道从哪里继续
        self.where = i
        return "".join(path)

算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 核心技巧：递归处理嵌套 + 字符串重复

---

题目三：含有嵌套的分子式求原子数量

问题描述

给你一个字符串化学式 formula，返回每种原子的数量。

• 原子总是以一个大写字母开始，接着跟随0个或任意个小写字母
• 如果数量大于1，原子后会跟着数字表示原子的数量
• 如果数量等于1则不会跟数字

测试链接：https://leetcode.cn/problems/number-of-atoms/

核心思想

递归解析嵌套分子式，返回原子计数字典

具体流程如下：

• 循环解析当前层级，直到遇到 ‘)’ 或字符串末尾。
• 解析过程中维护三个状态：name (当前原子名), pre (括号内解析结果的字典), cnt (倍数)。
• 当遇到下一个大写字母或左括号 ( 时，说明前一个“单元”（原子或括号）已经解析完毕，
  调用 _fill 函数将其信息合并到当前层级的总结果 ans 字典中。
• 遇到 (，递归调用 _f 获取括号内的原子构成，存入 pre 字典。
• 遇到大写字母，开始一个新的原子名 name。
• 遇到小写字母，追加到 name。
• 遇到数字，累加成倍数 cnt。

算法实现

from collections import defaultdict

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        """
        主函数，初始化共享索引并启动递归，最后格式化输出
        """
        self.where = 0
        # 调用递归函数获取原子计数的字典
        atom_map = self._f(list(formula), 0)
        
        # 构建最终的输出字符串
        ans = []
        # 按原子名称的字母顺序排序，返回有序表
        for key in sorted(atom_map.keys()):
            ans.append(key) # 先添加原子名称再添加数量
            cnt = atom_map[key]
            if cnt > 1:
                ans.append(str(cnt))
        return "".join(ans)

    def _f(self, s: list, i: int) -> dict:
        """
        递归函数，解析一个层级的分子式，返回一个字典
        """
        ans = defaultdict(int)  # 创建默认字典
        name = []  # 存储当前原子名称
        pre = None  # 历史记录
        cnt = 0
        
        while i < len(s) and s[i] != ')':
            if 'A' <= s[i] <= 'Z' or s[i] == '(':
                # 遇到新单元，先把之前收集的信息处理掉
                self._fill(ans, name, pre, cnt)
                # 重置状态
                name.clear()  # 清空列表中的所有元素
                pre = None
                cnt = 0  # 重置倍数
                
                if 'A' <= s[i] <= 'Z':
                    name.append(s[i])
                    i += 1  # 移动到下一个字符
                else:  # 遇到 (
                    # 递归处理括号内的表达式
                    pre = self._f(s, i + 1)
                    i = self.where + 1
            elif 'a' <= s[i] <= 'z':
                name.append(s[i])
                i += 1
            else:  # 遇到数字
                cnt = cnt * 10 + int(s[i])
                i += 1
        
        # 循环结束，处理最后一个单元
        self._fill(ans, name, pre, cnt)
        # 更新全局索引
        self.where = i
        return ans

    def _fill(self, ans: dict, name: list, pre: dict, cnt: int):
        """辅助函数，将一个解析完的单元（原子或括号）合并到总结果中"""
        if name or pre:
            # 如果没有数字，倍数默认为1
            cnt = 1 if cnt == 0 else cnt
            if name:
                # 如果是原子，直接累加数量
                key = "".join(name)
                ans[key] += cnt
            else:  # 如果是括号内的字典 pre
                # 遍历字典，将其中每个原子的数量乘以倍数 cnt，再累加
                for key, val in pre.items():
                    ans[key] += val * cnt

算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 核心技巧：递归处理嵌套 + 字典合并

---

核心套路总结

1. 递归函数设计模板

class Solution:
    def solve(self, s: str):
        """主函数，初始化全局变量"""
        self.where = 0
        return self._f(list(s), 0)
    
    def _f(self, s: list, i: int):
        """递归函数核心模板"""
        # 初始化当前层级的状态变量
        result = []  # 或其他适当的数据结构
        
        while i < len(s) and s[i] != 终止条件:
            if 普通字符处理:
                # 直接处理
                i += 1
            elif 嵌套开始标志:
                # 递归调用处理嵌套
                nested_result = self._f(s, i + 1)
                # 处理递归结果
                result.append(nested_result)
                # 更新位置
                i = self.where + 1
            else:
                # 其他情况处理
                i += 1
        
        # 更新全局位置
        self.where = i
        return result

2. 全局变量where的作用

# where的三个关键作用：
# 1. 记录当前递归函数解析到的位置
# 2. 让上级函数知道下级函数处理到哪里了
# 3. 实现递归层级之间的位置传递

3. 嵌套处理的通用策略

# 遇到嵌套开始标志时：
if s[i] == '(' or s[i] == '[':  # 根据具体问题调整
    # 1. 递归调用处理嵌套内容
    nested_result = self._f(s, i + 1)
    
    # 2. 处理递归返回的结果
    process_nested_result(nested_result)
    
    # 3. 更新当前位置到嵌套结束后
    i = self.where + 1

复杂度分析总结

题目	时间复杂度	空间复杂度	核心数据结构
表达式求值	O(n)	O(n)	列表 + 递归栈
字符串解码	O(n)	O(n)	字符串 + 递归栈
分子式解析	O(n)	O(n)	字典 + 递归栈

学习建议

1. 理解递归本质

• 递归是处理嵌套结构的自然选择
• 每一层递归负责处理一个层级的内容
• 通过全局变量实现层级间的信息传递

2. 掌握状态管理

• 明确每层递归需要维护哪些状态
• 合理设计辅助函数处理复杂逻辑
• 注意状态的重置和更新时机

3. 练习边界处理

• 递归终止条件的设计
• 嵌套边界的正确处理
• 特殊情况的考虑（空字符串、单字符等）

4. 优化技巧

• 使用合适的数据结构（列表、字典、栈等）
• 避免重复计算和冗余操作
• 考虑空间复杂度的优化

5. 调试方法

• 画出递归调用的层级关系图
• 追踪全局变量where的变化
• 验证每层递归的输入输出

通过掌握这个通用的嵌套类问题解题套路，可以有效解决包含括号、方括号等嵌套结构的各类算法问题。关键在于理解递归的层级关系和全局变量的作用机制。