2021-12-13：字符串解码。给定一个经过编码的字符串，返回

原创

福大大架构师每日一题

发布于 2021-12-13 14:05:03

4270

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-12-13：字符串解码。给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: kencoded_string，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 24 的输入。力扣394。

答案2021-12-13：

递归。递归还是有两个返回值。一个是返回结果，一个是返回序号。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    s := "2[moonfdd3[a]]2[]"
    ret := decodeString(s)
    fmt.Println(ret)
}

func decodeString(s string) string {
    str := []byte(s)
    return process(str, 0).ans
}

type Info struct {
    ans  string
    stop int
}

func NewInfo(a string, e int) *Info {
    ret := &Info{}
    ret.ans = a
    ret.stop = e
    return ret
}

// s[i....]  何时停？遇到   ']'  或者遇到 s的终止位置，停止
// 返回Info
// 0) 串
// 1) 算到了哪
func process(s []byte, i int) *Info {
    //StringBuilder ans = new StringBuilder();
    ans := make([]byte, 0)
    count := 0
    for i < len(s) && s[i] != ']' {
        if (s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z') {
            ////ans.append(s[i++]);
            ans = append(ans, s[i])
            i++
        } else if s[i] >= '0' && s[i] <= '9' {
            count = count*10 + int(s[i]) - int('0')
            i++
        } else { // str[index] = '['
            next := process(s, i+1)
            //ans.append(timesString(count, next.ans));
            ans = append(ans, timesString(count, next.ans)...)
            count = 0
            i = next.stop + 1
        }
    }

    return NewInfo(string(ans), i)
}

func timesString(times int, str string) string {
    ans := make([]byte, 0)
    for i := 0; i < times; i++ {
        ans = append(ans, str...)
    }
    return string(ans)
}