Leetcode 394.字符串编码
2024-09-04 13:50:44
字符串编码
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
求解
本题中明显有括号的匹配问题,因此需要使用栈来求解。当碰到右括号(])时,字符串出栈,碰到左括号([)时,保存左右括号内的字符串([]),继续出栈,保存字符串重复次数,直至栈为空或碰到非数字。要注意重复次数不是个位数,将字符串重复之后压入栈中。继续处理剩余字符串,同样执行上述过程,直至处理完字符串。然后将栈中所有的字符出栈构成结果字符串返回。
import java.util.Stack; public class Solution{
public String decodeString(String s){
int n=s.length();
Stack<Character> stack=new Stack<Character>();
String result="";
String temp="";
for(int i=0;i<n;i++){
char str=s.charAt(i);
if(str!=']'){
stack.push(str);
}else{
char ch=stack.pop();
while(ch!='['){
temp=ch+temp;
ch=stack.pop();
}
String times="";
while(!stack.isEmpty()){
ch=stack.pop();
if(Character.isDigit(ch)){
times=ch+times;
}else{
stack.push(ch);
break;
}
}
for(int j=0;j<Integer.parseInt(times);j++){
for(int k=0;k<temp.length();k++){
stack.push(temp.charAt(k));
}
}
temp="";
}
}
while(!stack.isEmpty()){
result=stack.pop()+result;
}
return result;
}
}
最新文章
- HTML解析组件HtmlAgilityPack使用
- 大话redis/memcache缓存
- Java基础(43):Java中的Object类与其方法(转)
- java学习系列(一)Java中的IO操作
- GITHUB基础使用教程
- nginx+gridfs+mongodb 配置访问png图片显示无法加载问题
- c#委托事件入门--第一讲:委托入门
- Java辅助类持续汇总~
- velocity模板引擎 -- java.io.FileNotFoundException: velocity.log (Permission denied)
- APIView流程——请求方式分发
- dp方法论——由矩阵相乘问题学习dp解题思路
- Spark学习之路 (十四)SparkCore的调优之资源调优JVM的GC垃圾收集器
- oracle与infomix异同点
- 第一篇 数据库MySql
- Java并发-Runnable、Callable、Future、Future Task
- Spyder kernel died 错误
- idea maven 依赖问题
- Python新式类 单例模式与作用域(四)
- webpack——概念的引入
- uoj problem 21 缩进优化