394. 字符串解码

394. 字符串解码

解题思路

1 利用栈，空间换时间 countStack 记录当前的次数 alphaIndex记录当前开始的字母索引，alphaStack记录字母， 按照 次数[ 字母…] 为一个字母段，执行入栈和出栈
2 当是”]” 出栈处理，出栈按照一个字母段为部分 索引需要记录从什么位置开始出栈 也就是alphaIndex的值作用。
3 数字可能是多位数字 需要利用count =count*10 +int(s[i]-‘0’) 计算当前的字母段出现的次数

func decodeString(s string) string {
    alphaStack := make([]byte, 0)
    countStack := make([]int,0)
    alphaIndex := make([]int,0)
    var count int
    for i:=0 ;i < len(s);i++{
        if s[i] >='0'&&s[i]<='9' {
            count =count*10 +int(s[i]-'0')
        }else  if s[i]=='['{ // [ 后面肯定是字母
            // 可以把当前的数字放入次数数组
            countStack = append(countStack,count)
            count =0
            alphaIndex = append(alphaIndex,len(alphaStack))
        }else if s[i] ==']'{ // 对当前字母段出站
            // 获取当前字母段的次数 然后次数出栈
            c :=countStack[len(countStack)-1]
            countStack = countStack[:len(countStack)-1]
            // 获取当前字母段开始的索引 然后索引出栈
            index :=alphaIndex[len(alphaIndex)-1]
            alphaIndex = alphaIndex[:len(alphaIndex)-1]
            //获取当前的字母段
            str := string(alphaStack[index:])
            // 字母数组出站
            alphaStack = alphaStack[:index]
            for j:=0;j<c;j++{
                alphaStack = append(alphaStack,[]byte(str)...)
            }
        }else {
            alphaStack = append(alphaStack,s[i])
        }
    }
    return string(alphaStack)
}