原题
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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”.
解法
思想
DFS，只处理字符串中不包含括号的，遇到带括号的将其分解。
代码
class Solution {
public String decodeString(String s) {
return multify(1,s);
}
public String multify(int repeat,String s){
StringBuilder sb = new StringBuilder();
//字符串中不带括号
if(s.indexOf('[') == -1){
for(int i = 0;i<repeat;i++){
sb.append(s);
}
return sb.toString();
}else{
//未匹配括号的个数
int count = 0;
//第一个数字出现的index
int firstNumberIndex = 0;
//第一个左括号出现的index
int firstLeftIndex = 0;
boolean firstNumberHasShown = false;
for(int i = 0;i<s.length();i++){
//如果是数字记录第一个数字出现的index
if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
if(firstNumberHasShown == false){
firstNumberIndex = i;
firstNumberHasShown = true;
}
}
//如果是左括号记录第一个左括号出现的index
else if(s.charAt(i) == '['){
if(count == 0)
firstLeftIndex = i;
count ++;
}
//如果是右括号则未匹配的左括号数量减一，如果全部匹配完则把repeat和substring递归处理。
else if(s.charAt(i) == ']'){
count --;
if(count == 0) {
firstNumberHasShown = false;
int repeatNum = Integer.valueOf(s.substring(firstNumberIndex,firstLeftIndex));
String subString = s.substring(firstLeftIndex+1,i);
sb.append(multify(repeatNum,subString));
}
}
else if(count==0){
sb.append(s.charAt(i));
}
}
}
return multify(repeat,sb.toString());
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode394-%e5%ad%97%e7%ac%a6%e4%b8%b2%e8%a7%a3%e7%a0%81/
