BFE.devAI解答 - JavaScript 代码题
174. 解压字符串

解法一：递归

可以通过递归来实现解压字符串。

首先，可以找到第一个左括号的位置，确定它的内部子字符串。然后，可以找到与这个左括号匹配的右括号的位置，用递归来计算这个子字符串的解压字符串。最后，使用重复操作符（repeat）将解压后的字符串重复所需的次数，并与之前的字符串连接起来。

具体实现见代码注释。

时间复杂度：$O(n^2)$，其中 $n$ 为输入字符串的长度。在最坏情况下，需要计算 $n$ 个递归函数，每个递归函数调用 $n$ 次字符串拼接操作。

空间复杂度：$O(n)$。递归调用时，需要调用栈空间，栈的深度最大为字符串长度。此外，需要维护当前解压的子字符串，字符串长度不超过 $n$。因此，总空间复杂度为 $O(n)$。

function uncompress(s) {
  let i = 0;
  let res = '';
  while (i < s.length) {
    if (s[i] >= '0' && s[i] <= '9') {
      // 处理数字
      let j = i + 1;
      while (j < s.length && s[j] >= '0' && s[j] <= '9') {
        j++;
      }
      const cnt = Number(s.substring(i, j)); // 数字的数量
      i = j;

      // 处理括号内的子字符串
      let brackets = 1;
      j = i + 1;
      while (j < s.length && brackets > 0) {
        if (s[j] === '(') {
          brackets++;
        } else if (s[j] === ')') {
          brackets--;
        }
        j++;
      }
      const subStr = s.substring(i + 1, j - 1); // 括号内的子字符串
      i = j;

      // 递归计算子字符串
      const uncompressedSubStr = uncompress(subStr);

      // 重复字符串并连接
      res += uncompressedSubStr.repeat(cnt);
    } else {
      // 普通字符直接连接
      res += s[i];
      i++;
    }
  }
  return res;
}

解法二：栈

也可以通过在栈中维护之前已经解压的子字符串和重复次数来实现解压字符串。

具体实现步骤如下：

1. 初始化一个栈。
2. 将栈顶元素视为当前子字符串的一部分，将当前字符加入该子字符串。
3. 如果遇到数字，则继续读取数字，直到数字结束，并将数字转换为数字数。
4. 如果遇到左括号，则插入（0，0）作为子字符串重复次数和子字符串的初始值，并将子字符串重置为空字符串。
5. 如果遇到右括号，则弹出栈顶元素并使用其存储的值扩展子字符串，此后，使用栈顶元素重复次数和扩展字符串重复栈中子字符串的数量。
6. 最终，堆栈底部将存储解压后的字符串。

时间复杂度：$O(n)$，其中 $n$ 为输入字符串的长度。需要遍历整个字符串。

空间复杂度：$O(n)$。需要一个栈存储信息，栈的深度不超过 $\frac n 2$。因此，总空间复杂度为 $O(n)$。

function uncompress(s) {
  const stack = [];
  let repeat = 0;
  let currentStr = '';

  for (const c of s) {
    if (c >= '0' && c <= '9') {
      repeat = repeat * 10 + Number(c);
    } else if (c === '(') {
      stack.push([repeat, currentStr]);
      repeat = 0;
      currentStr = '';
    } else if (c === ')') {
      const last = stack.pop();
      currentStr = last[1] + currentStr.repeat(last[0]);
    } else {
      currentStr += c;
    }
  }

  return currentStr;
}