LC394. 字符串解码 decode-string
LC394. 字符串解码 decode-string
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。
示例 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]
v1-StringBuilder
思路
一种解法直接,但是不那么高效的方法。
通过 stringbuilder 记录字符信息。
遇到 ]
再往前处理
1)截取 []
中的字符,是需要重复的信息
2)重复的次数从 [
往前找到所有的数字,计算对应的次数
3)结果的处理更新
实现
public String decodeString(String s) {
String ans="";
for(char ch:s.toCharArray()){
if(ch==']'){
int end=ans.length();
int start=ans.lastIndexOf('[');
// 往前判断所有数字
int i=start-1;
int count=0;
while(i>=0&&Character.isDigit(ans.charAt(i))){
count=((ans.charAt(i)-'0')*(int)Math.pow(10,start-1-i)+count);
i--;
}
ans=ans.substring(0,i+1)+ans.substring(start+1,end).repeat(count);
}else{
ans+=ch;
}
}
return ans;
}
效果
11ms 击败 23.65%
反思
按理说是可以更快地。
v2-两个栈
思路
整体思路一样,不过我们可以借助栈,让流程看起来清晰一点。
只有两个部分需要关心:
1)次数
2)需要次数处理的字符串片段
处理流程
针对每一个字符,分为四个场景:
1)数字
更新 num
num = num * 10 + (c - '0');
[
说明普通字符结束,数字也结束。
numStack.push(num);
strStack.push(cur);
num = 0;
cur = new StringBuilder();
]
处理需要重复的部分
StringBuilder pre = strStack.pop();
int times = numStack.pop();
for(int i = 0; i < times; i++) {
pre.append(cur);
}
// 当前字符更新
cur = pre;
- 其他字符
正常添加
cur.append(c);
实现
public String decodeString(String s) {
Stack<Integer> numStack = new Stack<>();
Stack<StringBuilder> strStack = new Stack<>();
StringBuilder cur = new StringBuilder();
int num = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
} else if (ch == '[') {
numStack.push(num);
strStack.push(cur);
cur = new StringBuilder(); // 新的子串
num = 0;
} else if (ch == ']') {
int times = numStack.pop();
StringBuilder prev = strStack.pop();
for (int i = 0; i < times; i++) {
prev.append(cur);
}
cur = prev;
} else {
cur.append(ch);
}
}
return cur.toString();
}
效果
1ms 击败 74.27%
反思
还能更快吗?
v3-数字模拟
思路
还是用数组模拟,避免拆箱、装箱,集合创建的开销。
实现
public String decodeString(String s) {
int n = s.length();
int[] countStack = new int[n];
StringBuilder[] strStack = new StringBuilder[n];
int top = -1;
StringBuilder cur = new StringBuilder();
int num = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
} else if (ch == '[') {
countStack[++top] = num;
strStack[top] = cur;
cur = new StringBuilder();
num = 0;
} else if (ch == ']') {
int times = countStack[top];
StringBuilder prev = strStack[top--];
prev.append(cur.toString().repeat(times));
cur = prev;
} else {
cur.append(ch);
}
}
return cur.toString();
}
效果
0ms 击败 100.00%