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
    }
}
我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章