# JAVA, recursive method, with detailed explaining 3ms

• ``````public class Solution {
/*
* Thoughtway:
* Decode the string is to unzip the compressed part of the input string.
* e.g. a2["content"]c ==> a"content""content"c
* and "content" may go through the same process to get the pure string.
*
* Method: (Recursive: easy to code, but takes more stack memory)
* Scan the input string from index 0 to the end and append characters into the result.
* When encountering a digit :
*  1 parse the real value represents by it and its following digits, say "repeat" times.
*  2 find the index of the closing bracket corresponding to the open braket following the last digit in step 1
*      e.g. 8[3[hello]world] : the ']' folloing "world" is the closing bracket of '[' following 8
*  3 decode the substring between open and closing brackets by calling "decodeString", say "content"
*  4 append "content" to result "repeat" times
*  5 keep going to the end
*

* Analysis :
* real performance : 3ms
* in the worst case : time O(n2) space O(n2)
*/
public String decodeString(String s) {
int len = s.length();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i ++) {`
char ch = s.charAt(i);
if (Character.isLetter(ch)) {
sb.append(ch);
} else if (Character.isDigit(ch)) {
int start = i;
while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
i ++;
}
int repeatTime = Integer.parseInt(s.substring(start, i + 1));
int openLeft = 1;
i = i + 2;
start = i;
while (openLeft != 0) {
if (s.charAt(i) == '[') {
openLeft ++;
} else if (s.charAt(i) == ']') {
openLeft --;
}
i ++;
}
i --;
String repeatStr = decodeString(s.substring(start, i));
while (repeatTime -- > 0) {
sb.append(repeatStr);
}
}
}
return sb.toString();
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.