【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) stringf = func(i int) string { // 处理 [ 内部的结果path := "" // 当前函数的处理结果cnt := 0 // 倍数, 如 3[a] 中的 3for 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