字符串解码:给一个字符串,返回解码后的字符串。
题目
字符串解码,给一个字符串s,返回解码后的字符串。字符串编码规则为k[str]表示括号内部str字符串正好重复k次,k保证为整数,并且输入的字符串肯定符合这种编码规则不会有额外的空格。
注意事项:
- 注意括号可能发生嵌套,例如输入字符串为
3[a2[c]]
应该返回accaccacc - 1 <= s.length <= 30
- s由小写英文字母、数字和方括号'[]' 组成
- s保证是一个有效的输入。左括号前肯定指明了重复次数,对于不重复的字符串不会用括号将它括住。
- s中所有整数的取值范围为[1, 300]
输入输出
输入 | 输出 |
---|---|
3[a]2[bc] | aaabcbc |
abc3[d2[e]] | abcdeedeedee |
初步分析
因为嵌套括号的可能性,所以这道题需要使用数据结构栈,一个栈保存数字代表重复的次数,一个栈保存当前需要重复拼接的字符串。
我的思路
使用List集合存储每个数字,然后没有考虑到临时字符串的存储。没有理解到这道题的核心思想:当发生嵌套括号时,需要从最内层的元素向外拼接。从内向外。
题解思路
countStack
栈存储需要重复的次数,stringStack
栈存储当前的临时字符串。- 创建StringBuilder对象curStr为当前拼接的字符串,用于应对连续字符的情况,例如
2[abc]
- 创建整形count记录每个重复次数,例如
2[a3[b]]
则压栈顺序为:2--->3 - 将目标字符串转为char数组进行遍历,依次判断每个字符情况。
- 最终curStr是拼接完成的,解密后的字符串,返回。
关键点
第四步,遇到特定字符该做什么?
我们先假设最理想情况:e10[a]3[b]abc
//首先判断字符是数字的情况
if(Character.isDigit(ch)){
//将字符转为对应的10进制数字,因为重复次数范围在1~300
int count = 0;
count = count * 10 + ch - '0';
//但这里不能判断是否应该将count压栈,因为无法确定ch后面是否还有数字
}
//2.判断ch = '['情况
if(ch == '['){
//匹配到左括号,肯定代表count已经固定得到了,将其压栈
countStack.push(count);
//因为第一个左括号前可能有未在括号内的字符串,也就是重复次数为1的字符串,所以需要将当前字符串压栈
stringStack.push(curStr);
//当前字符串已记录,让其恢复为空字符串
curStr = new StringBuilder();
//count也需要还原
count = 0;
}
//3.判断ch是字母的情况
if(Character.isLetter(ch)){
curStr.append(ch);
}
//4.判断ch = ']'右括号
if(ch == ']'){
//每当匹配到右括号,算是一个终结条件,无论多少个括号嵌套,当匹配到右括号时后面一定都是右括号直到结束
/*当前栈、curStr、count的情况
countStack [10]
stringStack ["e"]
curStr "a"
count 0
*/
//观察本次输入范例,我们需要在e后面拼接10个a字符
count = countStack.pop();
StringBuilder temp = new StringBuilder(stringStack.pop());
for(int i=0;i<count;i++){
temp.append(curStr);
}
curStr = temp;
count = 0;
}
根据上面代码我们再分析这种情况a2[b3[c]]
结果应该为abcccbccc
//第一次匹配到]
/*
countStack [2,3] 栈顶为3
stringStack ["a","b"] 栈顶为"b"
curStr "c"
count 0
*/
//第二次匹配到]
/*
countStack [2] 栈顶为2
stringStack ["a"] 栈顶为"a"
curStr "bccc"
count 0
*/
//第二次执行完后
curStr = "abcccbccc"
图解
代码
public class DecodeStr {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
System.out.println(getResult(str));
}
private static String getResult(String s) {
Stack<Integer> countStack = new Stack<>();
Stack<String> stringStack = new Stack<>();
//最终返回的就是他
StringBuilder curStr = new StringBuilder();
int count = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)){
count = count * 10 + (c - '0');
}else if (c == '['){
countStack.push(count);
stringStack.push(curStr.toString());
curStr = new StringBuilder();
count = 0;
}else if (c == ']'){
//找到了最内部的字符串,从stringStack中弹出
StringBuilder decodedString = new StringBuilder(stringStack.pop());
//寻找该字符串重复次数
int repeatCount = countStack.pop();
for (int i = 0; i < repeatCount; i++) {
decodedString.append(curStr);
}
curStr = decodedString;
}else {
curStr.append(c);
}
}
return curStr.toString();
}
}