LeetCode 394:字符串解码

2023-12-31 21:44
文章标签 leetcode 字符串 解码 394

本文主要是介绍LeetCode 394:字符串解码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目描述

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

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

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

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

示例 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] 

二、思路分析

注意示例 2 ,发现字符串中存在括号内有嵌套括号的情况,这个时候,只有先把内层括号解码成功,才能再去解码外层括号。意味着后面访问的括号比前面访问的括号还更早的进行处理,与栈的先入后出特点对应。所以本题可以使用栈的方式来进行解答。

1、构建两个栈,一个是数字栈 numStack ,在遍历字符串过程中记录出现的数字;一个是字符串栈 strStack ,在遍历字符串过程中记录出现的字符串。

2、初始化两个变量,一个是 digit ,用来记录访问到字符串之前出现的数字;一个是 result ,在访问编码字符串的过程中,把得到的结果存放到 result 中。

3、接下来,开始从头到尾遍历字符串,在遍历过程中,字符会出现 4 种情况,即数字、字符、"["、"]" 。

4、如果是数字,需要把字符转成整型数字,然后更新到 digit 上,代表后续的字符串需要重复 digit 次。

5、如果是字符,说明它就出现一次,可以直接存放到 result 中。

6、如果是 "[" ,这个时候出现了嵌套的内层编码字符串,而外层的解码需要等待内层解码的结果,那么之前已经扫描的字符需要存放起来,等到内层解码之后再重新使用。

7、如果是 "]" ,此时,内层解码已经有结果,需要把它和前面的字符串进行拼接。

8、拼接的方式就是先通过 numsStack 的栈顶元素获取重复的次数,再通过 strStack 的栈顶元素获取前面的字符串。

9、最后返回 result 。

三、代码参考

1、Java

class Solution {public String decodeString(String s) {// 创建数字栈,在遍历编码字符串过程中记录出现的数字Deque<Integer> numStack = new LinkedList<>();// 创建字符栈,在遍历编码字符串过程中记录出现的字符串Deque<StringBuilder> strStack = new LinkedList<>();// 在遍历字符串的过程中,用来记录访问到字符串之前出现的数字,一开始为 0int digit = 0;// 在遍历字符串的过程中,把得到的结果存放到 result 中StringBuilder result = new StringBuilder();// 循环遍历for (int i = 0; i < s.length(); i++) {// 获取访问的字符char ch = s.charAt(i);// 判断是否为数字字符if (Character.isDigit(ch)) {// 将字符转成整型数字 ch-‘0’// 补充:将字符'0'-'9'转换为数字,只需将字符变量减去'0'就行,因为字符和数字在内存里都是以 ASCII 码形式存储的,减去 '0' ,其实就是减去字符 '0' 的 ASCII 码,而字符 '0' 的 ASCII 码是 30,然后就可以得到字符对应的数字了int num = ch - '0';// 根据提示可知整数的取值范围是三位数,所以存在多位数,需要需要进行数字组合digit = digit * 10 + num ;}// 判断是否是字符else if((ch >= 'a' && ch <= 'z') ){// 说明它就出现一次,可以直接存放到 result 中result.append(ch);}// 判断是否是 "[" else if (ch == '[') {// 把数字存放到数字栈numStack.push(digit);// 把外层的解码字符串存放到字符串栈strStack.push(result);// 开始新的一轮解码,digit 归零digit = 0;// result 重新初始化result = new StringBuilder();}// 判断是否是"]" else if (ch == ']') {// 通过数字栈获取次数int count = numStack.poll();// 通过字符串栈获取之前的解码字符串StringBuilder outString = strStack.poll();// 循环把内层解码的字符串拼接起来for (int j = 0; j < count; j++) {// 拼接到 outString 后面,拼接 count 次outString.append(result.toString());}// 再把得到的结果赋值给 resultresult = outString;}}// 返回结果return result.toString();}
}

2、Python

class Solution(object):def decodeString(self, s):# 创建数字栈,在遍历编码字符串过程中记录出现的数字numStack = []# 创建字符栈,在遍历编码字符串过程中记录出现的字符串strStack = []# 在遍历字符串的过程中,用来记录访问到字符串之前出现的数字,一开始为 0digit = 0# 在遍历字符串的过程中,把得到的结果存放到 result 中result = ""# 循环遍历for ch in s:# 判断是否为数字字符if '0' <= ch <= '9':# 将字符转成整型数字num = int(ch)# 根据提示可知整数的取值范围是三位数,所以存在多位数,需要需要进行数字组合digit = digit * 10 + num # 判断是否是字符elif ch >= 'a' and ch <= 'z':# 说明它就出现一次,可以直接存放到 result 中result += ch# 判断是否是 "[" elif ch == '[' :# 把数字存放到数字栈numStack.append(digit)# 把外层的解码字符串存放到字符串栈strStack.append(result)# 开始新的一轮解码,digit 归零digit = 0# result 重新初始化result = ""# 判断是否是"]" elif ch == ']':# 通过数字栈获取次数count = numStack.pop()# 通过字符串栈获取之前的解码字符串outString = strStack.pop()# 循环把内层解码的字符串拼接起来for j in range(0,count) : # 拼接到 outString 后面,拼接 count 次outString += result# 再把得到的结果赋值给 resultresult = outString# 返回结果return result

这篇关于LeetCode 394:字符串解码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/557208

相关文章

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为