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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划

C和指针:字符串

字符串、字符和字节 字符串基础 字符串就是一串零个或多个字符,并且以一个位模式为全0的NUL字节结尾。 字符串长度就是字符串中字符数。 size_t strlen( char const *string ); string为指针常量(const修饰string),指向的string是常量不能修改。size_t是无符号数,定义在stddef.h。 #include <stddef.h>