2023-9-21

9-21

栈

题号394. 字符串解码

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

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

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

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

辅助栈解法

function decodeString(s: string): string {
  let result = '';         // 存储解码后的结果
  let multi = 0;           // 用于记录数字倍数
  const multiStack: number[] = [];  // 用于记录倍数的栈
  const resStack: string[] = [];    // 用于记录部分结果的栈

  for (const char of s) {
    if (char === '[') {
      multiStack.push(multi);       // 将当前倍数压入栈
      resStack.push(result);        // 将部分结果压入栈
      multi = 0;                    // 重置倍数
      result = '';                  // 重置部分结果
    } else if (char === ']') {
      const curMulti = multiStack.pop();  // 弹出栈中的倍数
      const prevRes = resStack.pop();     // 弹出栈中的部分结果
      result = prevRes + result.repeat(curMulti); // 构建新部分结果
    } else if (char >= '0' && char <= '9') {
      multi = multi * 10 + parseInt(char); // 构建倍数
    } else {
      result += char;  // 添加字符到部分结果
    }
  }

  return result; // 返回最终解码结果
}

递归法

function decodeString(s: string): string {
  const dfs = (str: string, index: number): [string, number] => {
    let result = '';
    let multi = 0;

    while (index < str.length) {
      const char = str.charAt(index);

      if (char >= '0' && char <= '9') {
        multi = multi * 10 + parseInt(char);
      } else if (char === '[') {
        const [subStr, newIndex] = dfs(str, index + 1);
        index = newIndex;
        while (multi > 0) {
          result += subStr;
          multi--;
        }
      } else if (char === ']') {
        return [result, index];
      } else {
        result += char;
      }

      index++;
    }

    return [result, index];
  };

  return dfs(s, 0)[0];
}