题目描述
分析
1. 递归+循环
遍历 a. 若为数字，则记录数字大小，及数字位数 b. 若为 “[“(所在位子为左指针)，若还有数字，则递归调用a c. 若为 “]“(所在位子为右指针)，执行2[ab]->abab操作
代码实现
public enum Q394 {
instance;
public String decodeString(String s) {
if(s.length()==0) return s;
return decode(s, 0,0,0);
}
private String decode(String s,int repetition,int lPoint,int rPoint){
for(int i=lPoint;i<s.length();){
char c=s.charAt(i);
if(isNumber(c)){
// 重复执行次数
repetition= getNumByString(s,i);
// 位数 如:100->3
int digit = getDigit(repetition);
i+=digit;
return decode(s,repetition,i,rPoint);
}else if(c=='['){
// 左指针
lPoint=i;
}else if(c==']'){
// 右指针
rPoint=i;
if(lPoint<rPoint){
// 2[ab] -> abab
int digit=getDigit(repetition);
String merge = s.substring(lPoint+1, rPoint);
StringBuilder sb=new StringBuilder();
while (repetition>0){
sb.append(merge);
repetition--;
}
// 插入到字符中
s=s.substring(0,lPoint-digit)+sb.toString()+s.substring(rPoint+1);
// 可能会有2[ab],重头遍历
i=0;
continue;
}
}
i++;
}
return s;
}
private boolean isNumber(char c){
// [0-9]
return 48<=c&&57>=c;
}
private int getNumByString(String s, int point){
StringBuilder num= new StringBuilder();
for(int i=point;i<s.length();i++){
char c = s.charAt(i);
if(48<=c&&57>=c){
num.append(c);
}else {
break;
}
}
return Integer.valueOf(num.toString());
}
private int getDigit(int num){
int count=1;
while (num/10!=0){
count++;
num/=10;
}
return count;
}
public static void main(String[] args) {
// assert "acdcdacdcdacdcd"
SystemUtil.print(Q394.instance.decodeString("3[a2[cd]]"));
// assert "abcabccdcdcdef"
SystemUtil.print(Q394.instance.decodeString("2[abc]3[cd]ef"));
// assert "accaccacc"
SystemUtil.print(Q394.instance.decodeString("3[a2[c]]"));
// assert "aaabcbc"
SystemUtil.print(Q394.instance.decodeString("3[a]2[bc]"));
// assert "sdfeegfeegi"
SystemUtil.print(Q394.instance.decodeString("sd2[f2[e]g]i"));
// assert "leetcode"
SystemUtil.print(Q394.instance.decodeString("leetcode"));
SystemUtil.print(Q394.instance.decodeString("100[leetcode]"));
}
}
