字符串解码
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
1 2
| 输入:s = "3[a]2[bc]" 输出:"aaabcbc"
|
思路:如果遇到数字,直接累计count
,遇到字母.结果集直接append, 扫描字符串如果遇到'['
则寻找其对应的结束符号']'
,递归计算范围内的字符串,然后根据count和得到的字符串多次append.
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| class Solution { public String decodeString(String s) { if(s == null || s.isEmpty()){ return ""; } int length = s.length(); return calc(s, 0 , length - 1); } public int findEnd(String s, int start) { Stack stack = new Stack(); for(int i = start; i < s.length(); i++) { char c = s.charAt(i); if(c == '[') { stack.push(c); }else if(c == ']'){ stack.pop(); if(stack.isEmpty()) { return i; } } } return -1; } public String calc(String str, int start, int end) { StringBuilder ret = new StringBuilder(); StringBuilder count = new StringBuilder(); int i = start; while(i <= end){ char c = str.charAt(i); if(c >= '0' && c <= '9') { count.append(c); } else if(c == '[') { int tmp = findEnd(str, i); String ss = calc(str,i + 1,tmp - 1); if(!count.isEmpty()){ int num = Integer.parseInt(count.toString()); for(int k = 0; k < num; k++){ ret.append(ss); } } count = new StringBuilder(); i = tmp + 1; continue; } else { ret.append(c); } i++; } return ret.toString(); } }
|