2022-04-26.md

每日一题 - 字符串解码

信息卡片

• 时间：2022-04-26
• 题目链接：https://leetcode.com/problems/decode-string/
• tag：栈 递归 字符串

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例2：

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

示例3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300]

思路分析

1. 元组：数字[字符串]
   • 可以没有数字、中括号，则没有重复
2. 拆分字符串（例：3[a2[c]]）
   • 读取字符串，逐个压入栈 3 [ a 2 [ c ]
   • 直至遇到]开始进行出栈 ] c [ 2
   • 直至遇到[边上的数字，停止出栈得到的临时字符串 -> cc
   • 将临时字符串压入栈中
   • 继续读取原字符串 ]（重复上述过程）] cc a [ 3
     • 没遇到非 ] 字符就压栈
     • 遇到就出栈，直到遇到第一个[前一个数字
3. 原字符串读取完毕以及暂为空为止 accaccacc

参考答案

1. 基于栈 $O(n)$

空间复杂度：$O(n)$ 字符串长度为 n

function decodeString(s) {
  let stk = []
  let n = 0
  while(n < s.length) {
    let cur = s.charAt(n)
    if (!isNaN(cur)) {
      // 处理数字，可能是多位
      let [digits, m] = getDigits(s, n)
      n = m
      stk.push(digits)
    } else if (/[a-z]/.test(cur) || cur === '[') {
      // 处理小写英文字母和'['
      stk.push(s.charAt(n++))
    } else {
      // 处理']'，处理相匹配的'['之间的字符
      ++n
      // 将字符组合
      let subStk = []
      while('[' !== stk[stk.length - 1]) {
        subStk.push(stk[stk.length - 1])
        stk.pop()
      }
      // 因为栈的形式，组合的字符串与原本的字符串相比是倒序的，需要反转一次
      subStk = subStk.reverse()
      // '[' 出栈
      stk.pop()

      // 此时栈顶为当前 subStk 对应的字符串应该出现的次数
      let repTime = parseInt(stk.pop())
      let subString = ''
      while(repTime--) {
        subString += subStk.join('')
      }
      stk.push(subString)
    }
  }
  return stk.join('')
}
// 处理数字（多位）
function getDigits(s, n) {
  let ret = ''
  while(!isNaN(s.charAt(n))) {
    ret += s.charAt(n++)
  }
  return [ret, n]
}