嵌套类递归模版

基本步骤

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

例题分析

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

字符串中一共会出现四种情况：1.数字 2.字母 3.左括号 4.右括号

遇到数字和字母，我们可以记录下来。遇到左括号，说明我们进入到了一个嵌套，需要重复括号内的字符串，直到i扫描到右括号。

这个时候，上游的函数就可以接收下游函数传递的嵌套结果，进而通过数字进行重复。

代码如下：

int where = 0;

// 重复字符串
string repeat(int times, string s) {
	string res;
	for (int i = 0; i < times; ++i) {
		res += s;
	}
	return res;
}

string f(int i, string s) {
	int d = 0; // 用于记录数字
	string path; // 用于记录子串
	while (i < s.size() && s[i] != ']') {
		// 遇到数字
		if (s[i] >= '0' && s[i] <= '9') {
			d = d * 10 + (s[i++] - '0');
		}
		// 遇到字母
		else if (s[i] >= 'a' && s[i] <= 'z') {
			path.push_back(s[i++]);
		}
		// 遇到左括号
		else {
			path += repeat(d, f(i + 1, s));
			i = where + 1;
			d = 0;
		}
	}
	// 把当前的位置传给上游函数
	where = i;
	return path;
}

感谢

本文整理自左神的算法讲解039【必备】嵌套类问题的递归解题套路