Skip to main content

3-12 394. 字符串解码

Date：2022-03-12 14:08:50

标签：

  • 单调栈

题目：394. 字符串解码 ( 中等😕 )​

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

编码规则为: 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"

分析​

  • 栈

    一般左右对称的结构都可以用栈解决

    根据题目意思，有四种情况：

    • 数字

      记录当前数量，入栈需要，注意该数量可能不止一位数

    • [

      入栈，将 (数量, 当前收集到的字符串) 放入栈

      所以，栈中的结构只会是 (数量, 字符串)

    • ]

      出栈，计算结果，有两种情况

      • 栈中还有元素（说明是嵌套的）

        当前收集的字符串 = 出栈元素收集的字符串 + 当前收集的字符串 * 数量

      • 栈中没有元素了

        置空当前收集的字符串，并累加到结果中

    • 其他字符

      收集该字符串

    下面是 LeetCode 题解的一个图，比较生动

    image-20220312141657988

题解​

function decodeString111(s: string): string {
  const len = s.length
  let curr = '',
    currTime = '',
    ans = ''

  const stack: {
    times: number
    s: string
  }[] = []

  for (let i = 0; i < len; ++i) {
    // four case:
    // 1.number Record the number of
    // 2.char   Add temporary strings
    // 3.[      Into the stack
    // 4.]      Out of the stack

    console.log('[stack]:', stack)

    const time = Number(s[i])

    if (!isNaN(time)) {
      currTime += s[i]

      continue
    }

    const char = s[i]
    switch (char) {
      case '[':
        stack.push({
          times: Number(currTime),
          s: curr,
        })

        curr = ''
        currTime = ''
        break
      case ']':
        const { s, times } = stack.pop()

        const combined = s + repeat(curr, times)

        // exist element in stack, combined needs to enter the next calculation
        if (stack[stack.length - 1]) {
          curr = combined
        } else {
          curr = ''
          ans = ans + combined
        }

        break
      default:
        curr += char
        break
    }
  }

  // plus the trailing element
  return ans + curr

  function repeat(s: string, times: number) {
    let ans = ''
    for (let i = 0; i < times; ++i) {
      ans += s
    }

    return ans
  }
}

测试

function main() {
  // const s = '3[a]2[bc]'
  // const s = '3[a2[c]]'
  // const s = '2[abc]3[cd]ef'
  // const s = 'abc3[cd]xyz'
  // const s = '100[leetcode]'
  // const s = 'head1[3[a2[c]]]tail'
  // const s = '3[z]2[2[y]pq4[2[jk]e1[f]]]ef'

  // console.log('[]:', decodeString(s))
  console.log('[]:', decodeString111(s))
}

main()

export {}