394. Decode String
Given an encoded string, return it's decoded string.
The encoding rule is: k[encoded_string]
, where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a
or 2[4]
.
Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
算法分析
看到 3[a2[c]]
这样的字符串,显然要用到递归算法,就是要把 []
中间的字符串解析出来后,再由外面的数字决定重复次数。而解析 []
中的字符串的过程,就是调用解析函数的过程。对于一个 encoded string, 我们把它考虑成如下的格式: (head)(body)(tail)
其中,head 是纯字符序列(当然也可能为空字符序列),body 是形如 3[ab2[c]]
的序列,tail 是之后的尾端字符序列;tail 可以看做一个独立的 encoded string。我们首先解析出 head,然后对 body 里方括号内的字符串调用解析函数,将得到的字符串重复 body 里打头的数字次数;然后解析 tail ,最后将三者合并即可。
Java算法:
public class Solution {
public String decodeString(String s) {
if(s==null||s.length()==0)
return s;
char ch;
int index=0;
int repeat=0;
StringBuilder head=new StringBuilder(""),body=new StringBuilder("");
while(index<s.length()&&!Character.isDigit(ch=s.charAt(index))){
head.append(ch);
index++;
}
if(index<s.length()){
//indicating that next character is Digit
while(index<s.length()&&Character.isDigit(ch=s.charAt(index))){
repeat=repeat*10+ch-'0';
index++;
}//got the leading num
//now index is pointing to '[';
//next, to get the index of ']';
int rightBracket=index+1;
int leftBracketNum=1;
while(leftBracketNum>0){
ch=s.charAt(rightBracket);
if(ch==']'){
leftBracketNum--;
}
else if(ch=='['){
leftBracketNum++;
}
else{
}
rightBracket++;
}
rightBracket--;//now rightBracket is pointing to the right position of the ']';
String bodyStr=decodeString(s.substring(index+1,rightBracket));
String tail=decodeString(s.substring(rightBracket+1));
for(int i=1;i<=repeat;i++){
body.append(bodyStr);
}
body.append(tail);
}
return head.toString()+body.toString();
}
}
LeetCode赛题394----Decode String的更多相关文章
-
[LeetCode] 394. Decode String 解码字符串
Given an encoded string, return it's decoded string. The encoding rule is: k[encoded_string], where ...
-
【LeetCode】394. Decode String 解题报告(Python)
作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 栈 日期 题目地址:https://leetcode ...
-
Leetcode -- 394. Decode String
Given an encoded string, return it's decoded string. The encoding rule is: k[encoded_string], where ...
-
Python 解LeetCode:394 Decode String
题目描述:按照规定,把字符串解码,具体示例见题目链接 思路:使用两个栈分别存储数字和字母 注意1: 数字是多位的话,要处理后入数字栈 注意2: 出栈时过程中产生的组合后的字符串要继续入字母栈 注意3: ...
-
【leetcode】394. Decode String
题目如下: 解题思路:这种题目和四则运算,去括号的题目很类似.解法也差不多. 代码如下: class Solution(object): def decodeString(self, s): &quo ...
-
394. Decode String 解码icc字符串3[i2[c]]
[抄题]: Given an encoded string, return it's decoded string. The encoding rule is: k[encoded_string], ...
-
394 Decode String 字符串解码
给定一个经过编码的字符串,返回它解码后的字符串.编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次.注意 k 保证为正整数.你可以认 ...
-
394. Decode String
[题目] Total Accepted: 10087 Total Submissions: 25510 Difficulty: Medium Contributors: Admin Given an ...
-
LeetCode赛题395----Longest Substring with At Least K Repeating Characters
395. Longest Substring with At least K Repeating Characters Find the length of the longest substring ...
随机推荐
-
深入理解AOP
引子: AOP(面向方面编程:Aspect Oriented Programing)和IoC一样是Spring容器的内核,声明式事务的功能在此基础上开花结果.但是AOP和OOP差别较大,要很好地理解这 ...
-
[Angularjs]ng-class,ng-class-even,ng-class-odd
写在前面 最近在通过angularjs将数据绑定到前端,其中也涉及到很多新的东西,一些效果还是很有必要实现的.在使用中发现ng-class,ng-class-even.ng-class-odd的使用, ...
-
RMAN备份与恢复之spfile
1.备份spfile 有关控制文件及参数文件备份的几种形式: 单独备份控制文件及参数文件 RMAN> backup current controlfile; 备份数据文件时包含控制文件 RMAN ...
-
apply和call的区别在哪里
apply:方法能劫持另外一个对象的方法,继承另外一个对象的属性. Function.apply(obj,args)方法能接收两个参数obj:这个对象将代替Function类里this对象args:这 ...
-
sql server 查看表结构说明
select c.name as [字段名],t.name as [字段类型] ,convert(bit,c.IsNullable) as [可否为空] ,convert(bit,case when ...
-
poj 1007 纯水题 排序
#include<stdio.h> #include<string.h> #include<algorithm> #include<stdlib.h> ...
-
Maven中阿里云私服配置
在国内maven仓库连接速度太慢 ,虽然对于很多互联网企业和大中型软件公司,建个镜像是分分钟的事.但对于个人开发者确实是个问题.解决办法可以用阿里云的MAVEN私服.有两种方法: 1.在$MAVEN_ ...
-
Java中的按位运算
博客大搬家. 一.位运算符简介: 1.按位与&.如果两个整形数据 a.b 对应位都是1,则结果位才为1,否则为0,(int 最大值0x7fffffff ): int a = 0x7ffffff ...
-
移动端自动化测试-AppiumApi接口详解
Appium 初始化配置信息(Desired Capabilities),Desired Capabilities实际上就是一个字典,它主要用于向Appium Server提供初始化配置参数,如:想要 ...
-
正确计算linux系统内存使用率
参考:https://blog.gesha.net/archives/406/ 图中的例子很典型,就是:多数的linux系统在free命令后会发现free(剩余)的内存很少,而自己又没有开过多的程序或 ...