Link to LeetCode Problem

S1: 递归

https://camo.githubusercontent.com/cfacf3e8bb0851bd0b122e218ad63e5ab2abf6d23d439dadf638ecb72298de74/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f6465636f64655f737472696e675f747265652e706e67

n[string] 表示解析 [] 模板里面的内容，然后重复 n 次，即得到 n 个 string 拼接起来的字符串。

根据题意，[] 里面还可以再嵌套 [] ，例如 n[m[string]]。这种情况下，我们得先解析最内层的模板，重复 m 次，然后将 m * string 的结果作为外层模板的解析内容，再重复 n 次。

如果嵌套的层数更多，我们也是得先找到最内层的 []，就像洋葱一样，一层层剥开，然后再从内到外一层层解析和拼接。这种层层嵌套的描述很容易就让人想到了递归。

按照常规，写递归时不要过多考虑前后的递归函数，想好当前递归函数需要处理些什么就好了。

• 在每个递归函数里我们处理一段没有嵌套模版的字符串。
• 遇到英文字母时，进行简单的拼接。
• 遇到数字时，累加数字。
• 遇到 [ 时，说明接下来是一个嵌套模版，开始递归处理。递归处理嵌套模版结束后，我们回到了当前递归层级，需要的信息有两个：
  1. 嵌套模版的解码字符串
  2. 嵌套模版的结束坐标
• 获得嵌套模版的解码字符串后，重复 n 次拼接到当前层级的解码字符串中，接着从嵌套模版的结束坐标开始继续处理当前层级的字符串。
• 遇到 ] 时，说明处理当前层级模版的递归可以结束了，返回上一种情况需要的信息，解码字符串以及模版结束的坐标。

class Solution {
public:
    string decodeString(string s) {
        return decodeString(s, 0).first;
    }

    pair<string, int> decodeString(string s, int cur) {
        int k = 0;
        string decoded;
        while (cur < s.size()) {
            // 收集数字
            if (isdigit(s[cur])) {
                k = k * 10 + s[cur] - '0';
                cur++;
            }
            // 收集字母
            else if (isalpha(s[cur])) {
                decoded.push_back(s[cur]);
                cur++;
            }
            // 开始解析下一层嵌套
            else if (s[cur] == '[') {
                pair<string, int> res = decodeString(s, cur + 1);
                // 解析完嵌套模式后
                while (k-- > 0) {
                    decoded.append(res.first);
                }
                k = 0;
                cur = res.second;
            }
            // 结束当前递归
            else if (s[cur] == ']') {
                return {decoded, cur + 1};
            }
        }
        return {decoded, -1};
    }
};

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s, cur = 0) {
    let k = 0;
    let decoded = '';
    while (cur < s.length) {
        if (s[cur] === '[') {
            const [str, pos] = decodeString(s, cur + 1);
            decoded += str.repeat(k);
            k = 0;
            cur = pos;
        } else if (s[cur] === ']') {
            return [decoded, cur + 1];
        } else if (/[0-9]/.test(s[cur])) {
            k = k * 10 + parseInt(s[cur++]);
        } else {
            decoded += s[cur++];
        }
    }
    return decoded;
};