394. 字符串解码(Medium)

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。

样例

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

题解

栈，需要使用两个栈，一个栈压入数字，一个栈压入字符串。每当碰到 ] 的时候，同时弹出，每当碰到 [ 的时候，同时压入。

具体实现上来说

第一种思路

使用 cur_string，num_string 记录当前 字符 和 数字

• 当出现[ 的时候，将两个元素压入一个栈中，同时清空两个字符串。
• 当出现] 的时候，重复字符串。 首先从栈中取出 字符串(last_string) 和 乘数(multi)，注意，栈中存储的元素是 last_string，last 指的是在 [ 之前的字符串，不需要乘起来，multi 也是 [ 之前的数字，记录的是重复次数。
• 所以重复字符串的计算方式为：last_string + cur_string * multi
• 最后的结果是 cur_string

思路参考了：字符串解码（辅助栈法 / 递归法，清晰图解）

第二种思路

使用两个栈，stack_num(数字)，stack_str(字符)。每次存储的时候也会把 [ 存入进去，当遇到 ] 的时候，就不停给的出栈，直到遇到[为止。最后的结果都在栈里面了。

代码示例

第一种思路（Python）

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        cur_string, num_string = '', ''
        for char in s:
            if char == '[':
                stack.append((cur_string, num_string))
                num_string = ''
                cur_string = ''
            elif char == ']':
                last_string, multi = stack.pop()
                print(multi)
                cur_string = last_string + int(multi) * cur_string
            elif '0' <= char <= '9':
                num_string += char 
            else: 
                cur_string += char 
        return cur_string

第二种思路（Go）

import (
    "strconv"
    "strings"
)

func Pop(stack *[]string) string { // Pop 实现
    n := len(*stack)
    value := (*stack)[n - 1]
    (*stack) = (*stack)[: n - 1]
    return value
}

func decodeString(s string) string {
    stack_str := make([]string, 0)
	stack_num := make([]int, 0)
	num_string := ""
	n := len(s)
	for i:= 0; i < n; i++ {
		if s[i] <= '9' && s[i] >= '0' {
			num_string += string(s[i])
		}else if s[i] == '[' {
			num_int, error := strconv.Atoi(num_string)
			if error != nil { // 有可能碰到 ""
          num_int = 1
      }
			stack_num = append(stack_num, num_int)
			stack_str = append(stack_str, "[")
			num_string = ""
		}else if s[i] == ']' {
			multi_num := stack_num[len(stack_num) - 1] 
			stack_num = stack_num[:len(stack_num) - 1]
			p := Pop(&stack_str)
            cur_string := ""
			for p != "[" { // 不停的出栈，直到碰到 "["
				cur_string = p + cur_string
                p = Pop(&stack_str)
			} 
            fmt.Println(multi_num)
            stack_str = append(stack_str, strings.Repeat(cur_string, multi_num))
		}else {
			stack_str = append(stack_str, string(s[i]))
		}
	}
    // fmt.Println(stack_str)
    return strings.Join(stack_str, "") 
}