Java Simple Recursive solution

• the run time is 3 ms. And the method is really straight-forward: every time when you meet a number, it must be followed by [...], we just need to recursively call our method to decode "...", then repeat the result "num" times.

'''
public class Solution {
public String decodeString(String s) {

``````    if (s.length() == 0) return "";
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i ++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int digit_begin = i;
while (s.charAt(i) != '[') i++;
int num = Integer.valueOf(s.substring(digit_begin, i));
int count = 1;
int str_begin = i+1;
i ++;
while (count != 0) {
if (s.charAt(i) == '[') count ++;
else if (s.charAt(i) == ']') count --;
i ++;
}
i--;
String str = decodeString(s.substring(str_begin, i));
for (int j = 0; j < num; j ++) {
sb.append(str);
}
} else {
sb.append(c);
}
}
return sb.toString();
}
``````

}
'''

• Nice solution! Just a little modification based on yours:

``````    StringBuilder cur = new StringBuilder();
int num = 0;
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
} else if (s.charAt(i) == '[') {
//find the matching ]
int begin = i;
i++;
int count = 1;
while (count != 0) {
if (s.charAt(i) == '[') {
count++;
} else if (s.charAt(i) == ']') {
count--;
}
i++;
}
i--;

String substr = decodeString(s.substring(begin + 1, i));
for (int k = 0; k < num; k++) {
cur.append(substr);
}
num = 0;
} else {
cur.append(s.charAt(i));
}
}
return cur.toString();``````

• What is the time complexity?

• Thanks for sharing!
The code for finding the matching ']' could be optimized as follow to avoid several i++, i--.
Plus wondering if the time complexity is O(n)? For every time of the recursion we would iterate every character of the string. That would be n+(n-k)+(n-k-k)..... (number and brackets are roughly constant length), so still linear time?
And the space complexity is O(number of bracket pairs), am I correct?

``````           else if(s.charAt(i)=='['){
int begin=i;
int count=1;
while(count>0){
i++;
if(s.charAt(i)=='[')    count++;
if(s.charAt(i)==']')    count--;
}``````

• This post is deleted!

• Nice solution, a bit shorter one:

``````public class Solution {
int ptr=0;
public String decodeString(String s) {
return helper(s,1);
}
public String helper(String s, int dup){
String s_temp="",res="";
while(ptr<s.length()&&s.charAt(ptr)!=']'){
if(Character.isDigit(s.charAt(ptr))){
int num=0;
while(Character.isDigit(s.charAt(ptr))) num=num*10+s.charAt(ptr++)-'0';
ptr++;
s_temp+=helper(s,num);
}
else s_temp+=s.charAt(ptr++);
}
for(int i=0;i<dup;i++) res+=s_temp;
ptr++;
return res;
}
}
``````

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