【LeetCode】394、字符串解码

【LeetCode】394、字符串解码

一、递归: 嵌套类问题

1.1 递归: 嵌套类问题

// go
func decodeString(s string) string {
    // 如果遇到 嵌套括号的情况, 则递归
    // 可能连续多位数字, 则 通过 cur = cur * 10 + int(c - '0') 实现
    
    where := 0 // 全局变量, 记录嵌套过程已执行到的位置, 嵌套过程结束后从 where + 1 继续
    var f func(i int) string
    f = func(i int) string { // 处理 [ 内部的结果
        path := "" // 当前函数的处理结果
        cnt := 0 // 倍数, 如 3[a] 中的 3
        for i < len(s) && s[i] != ']' { // 字符串未遍历完 or 嵌套未结束
            c := s[i]
            if (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') {
                path += string(c)
                i++
            } else if c >= '0' && c <= '9' {
                cnt = cnt * 10 + int(c - '0')
                i++
            } else { // 即 c == '[', 需开启嵌套
                path += strings.Repeat(f(i+1), cnt)
                cnt = 0 // 清理现场
                i = where + 1 // 上级继续从 嵌套结束的位置 之后继续, 即 where + 1
            }
        }
        where = i // 更新全局变量, 从而让嵌套的上级从 where + 1 处继续
        return path
    }
    return f(0)
}

参考左神: 嵌套类问题 递归思路

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts