当前位置:网站首页>394. 字符串解码-辅助栈
394. 字符串解码-辅助栈
2022-04-23 17:32:00 【hequnwang10】
一、题目描述
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: 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"
二、解题
辅助栈
将字符串中的字符压入栈,如果不是右括号,则将字符压栈,如果遇到右括号,则出栈,保存[ ]括号中的字符,如果继续出栈是数字,则保存数字N,然后将[ ]复制N次,继续压栈。最后将栈中元素出栈即可。
class Solution {
public String decodeString(String s) {
Stack<Character> stack = new Stack<>();
for(char ch : s.toCharArray()){
if(ch != ']'){
//如果不是右括号 就进栈
stack.push(ch);
}else{
//如果遇到左括号 就出栈
//去除[ ]中的字符串
StringBuilder sb = new StringBuilder();
//判断栈是否为空 并且 栈的元素是否字符
while(!stack.isEmpty() && Character.isLetter(stack.peek())){
sb.append(stack.pop());
}
//将字符串翻转
String substr = sb.reverse().toString();
//遇到左括号,然后直接将左括号出栈
stack.pop();
//判断栈中的字符串是否为数字
sb = new StringBuilder();
while(!stack.isEmpty() && Character.isDigit(stack.peek())){
//如果为数字
sb.append(stack.pop());
}
int cnt = Integer.valueOf(sb.reverse().toString());
for(int i = 0;i<cnt;i++){
//将字符串拼接cnt次然后压栈
for(char subch : substr.toCharArray()){
stack.push(subch);
}
}
}
}
//将栈中的元素出栈
StringBuilder res = new StringBuilder();
while(!stack.isEmpty()){
res.append(stack.pop());
}
return res.reverse().toString();
}
}
可以优化一下,使用双栈
class Solution {
public String decodeString(String s) {
StringBuilder sb = new StringBuilder();
//保存字符串
Stack<StringBuilder> strstack = new Stack<>();
//保存数字
Stack<Integer> numstack = new Stack<>();
int sum = 0;
for(char ch : s.toCharArray()){
//四种情况 1、如果是数字 2、如果是正常的字符串 3、如果是左括号 4、如果是右括号
//1、如果是数字
if(Character.isDigit(ch)){
sum = sum * 10 + ch - '0';
}else if(Character.isLetter(ch)){
//2、如果是正常的字符串
sb.append(ch);
}else if(ch == '['){
//3、如果是左括号
strstack.push(sb);
numstack.push(sum);
//更新
sb = new StringBuilder();
sum = 0;
}else{
//4、如果是右括号
StringBuilder prestr = strstack.pop();
int cnt = numstack.pop();
for(int i = 0;i<cnt;i++){
prestr.append(sb);
}
sb = prestr;
}
}
return sb.toString();
}
}
其他:
class Solution {
public String decodeString(String s) {
//看到需要括号匹配就要想到栈
StringBuilder res=new StringBuilder();
int num=0;
//借助两个栈 用桶型的栈模拟一下就懂了
LinkedList<String> character=new LinkedList<>();
LinkedList<Integer> count=new LinkedList<>();
for (char c:s.toCharArray()){
//只有这四种可能
if (c=='['){
count.addLast(num);
character.addLast(res.toString());
//清空因为下次还要用
num=0;
res=new StringBuilder();
}
else if (c==']'){
StringBuilder temp=new StringBuilder();
int num1=count.removeLast();
for (int i = 0; i < num1; i++) {
temp.append(res.toString());
}
res=new StringBuilder(character.removeLast()+temp);
}
else if(c<='9'&&c>='0'){
num = num * 10 + c-'0';
}else{
res.append(c);
}
}
return res.toString();
}
}
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hequnwang10/article/details/124324809
边栏推荐
- 快时钟同步慢时钟域下的异步控制信号slow clk to fast clk
- Baidu Map Case - modify map style
- Allowed latency and side output
- Shell-awk命令的使用
- Simulation of infrared wireless communication based on 51 single chip microcomputer
- Learning record of uni app dark horse yougou project (Part 2)
- [WPF binding 3] listview basic binding and data template binding
- Deep understanding of control inversion and dependency injection
- Devexpress GridView add select all columns
- HCIP第五次实验
猜你喜欢
uni-app黑马优购项目学习记录(下)
RPC核心概念理解
Future 用法详解
PC电脑使用无线网卡连接上手机热点,为什么不能上网
Devexpress GridView add select all columns
基于51单片机红外无线通讯仿真
ASP. Net core JWT certification
Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
索引:手把手教你索引从零基础到精通使用
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
随机推荐
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
[二叉数] 二叉树的最大深度+N叉树的最大深度
Further optimize Baidu map data visualization
[simple understanding of database]
01 - get to know the advantages of sketch sketch
How to sort the numbers with text in Excel from small to large instead of the first number
1-4 configuration executable script of nodejs installation
How does matlab draw the curve of known formula and how does excel draw the function curve image?
STM32 entry development board choose wildfire or punctual atom?
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
SiteServer CMS5. 0 Usage Summary
EF core in ASP Generate core priority database based on net entity model
C# Task. Delay and thread The difference between sleep
Collection of common SQL statements
双指针进阶--leetcode题目--盛最多水的容器
Router object, route object, declarative navigation, programmed navigation
Simulation of infrared wireless communication based on 51 single chip microcomputer
Bottom processing of stack memory in browser
[related to zhengheyuan cutting tools]
Use of shell sed command