Decode String

题目介绍

LeetCode 394. Decode String。

复杂度

时间复杂度: O(n), 空间复杂度: O(n)

解题思路

1. 构建辅助栈 stack， 遍历字符串 s 中每个字符 c；
   • 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
   • 当 c 为字母时，在 ans 尾部添加 c；
   • 当 c 为 [ 时，将当前 multi 和 ans 入栈，并分别置空置 0：
     • 记录此 [ 前的临时结果 ans 至栈，用于发现对应 ] 后的拼接操作；
     • 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × […] 字符串。
     • 进入到新 [ 后，ans 和 multi 重新记录。
   • 当 c 为 ] 时，stack 出栈，拼接字符串 ans = $1 + $0 * ans，其中:
     • $1 是上个 [ 到当前 [ 的字符串，例如 “3[a2[c]]” 中的 a；
     • $0 是当前 [ 到 ] 内字符串的重复倍数，例如 “3[a2[c]]” 中的 2。
2. 返回字符串 res。

class Solution {
    func decodeString(_ s: String) -> String {
        var stack: [(Int, String)] = []
        var ans: String = ""
        var mulit: Int = 0
        for c in Array(s) {
            if c.isLetter {
                ans += String(c)
            } else if c.isNumber {
                mulit = mulit * 10 + Int(String(c))!
            } else if c == "[" {
                stack.append((mulit, ans))
                mulit = 0
                ans = ""
            } else if c == "]" {
                let temp = stack.popLast()!
                var repeatStr = ""
                for _ in 0..<temp.0 {
                    repeatStr += ans
                }
                ans = temp.1 + repeatStr
            }
        }
        return ans
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/04/08/DecodeString/