一天一道算法题（28）：字符串解码（栈）

394. 字符串解码

文章目录

• [394. 字符串解码](https://leetcode.cn/problems/decode-string/)
• • ==思路==
  • • – 单栈版
    • – 双栈版思路
  • 结语

给定一个经过编码的字符串，返回它解码后的字符串。

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

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

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

测试用例保证输出的长度不会超过 105。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300]

思路

• 这里的代码大家其实也没啥好看的，因为我写的太垃圾了，写的有些啰嗦，主要是给大家提供思路，然后写出更好的代码

– 单栈版

• 给大家一个图，大家来跟着思考

• 当当前的元素不是“]”的时候，就一直压栈
• 遇到“]”的时候，取出“【】”之间的字符串
• 取出完字符串之后对“[”也出栈，然后出栈数字，取出数字
• 根据该数字再次压栈number次连续字符串
• 循环至s字符串遍历结束，此时stack（栈）里面就是答案，做一个类型转换之后就可以返回答案了

• 

– 双栈版思路

• 上面这个是单栈版本，还有双栈版本。我们可以存在两个栈，一个是数字栈，专门放数字，一个是字符栈，放“[ ]”和字符串，压栈和出栈没啥难点，但是有一个要思考的是怎么处理数字栈，因为这道题的数字不只是单位数，根据题目说明，这道题的整数范围是1~300，所以我们必须用一个分隔符确定每一次要取出的数字是什么，这里我给出的解决方案是在遍历到“[”的时候给数字栈压入0，作为分割符，代码的话就请大家自行思考吧

• 单栈版本代码展示

  func decodeString(s string) string {
  stack := []rune{}

  for _, v := range s {
  if v == ']' {
  var str []rune
  var num int
  //取出连续字符
  str, stack = popStr(stack)
  //取出连续数字
  num, stack = popInt(stack)

  for i := 0; i < num; i++ {
  //循环num次再次压栈
  stack = append(stack, str…)
  }
  } else {
  //如果不是"]"就压栈
  stack = append(stack, v)
  }
  }

  return string(stack)
  }

  func popInt(stack []rune) (int, []rune) {
  // 从后往前收集数字
  digits := []rune{}
  i := len(stack) – 1
  for i >= 0 && stack[i] >= '0' && stack[i] <= '9' {
  digits = append([]rune{stack[i]}, digits…)
  i—
  }
  num, _ := strconv.Atoi(string(digits))
  return num, stack[:len(stack)–len(digits)]
  }

  func popStr(stack []rune) ([]rune, []rune) {
  //从后往前收集字符串
  chars := []rune{}

  i := len(stack) – 1
  for i >= 0 && stack[i] != '[' {
  chars = append([]rune{stack[i]}, chars…)
  i—
  }

  return chars, stack[:i]
  }

结语

本题还可以使用递归的方式去写，但是因为最近的题目主要是以讲解栈的应用，所以这里就不做解释了

本文是 《算法题目解析系列》 的第 [28] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。