Iterative Java solution with explanation, 4ms

• We need to be careful about integers greater than 9 and also pushing the entire substring between the parenthesis at a time. Using a stack will makes things easy and we can do it using a single stack instead of storing integers in one stack and partial strings in another.
PS: Further improvements and suggestions will be appreciated.

``````public class Solution {
public String decodeString(String s) {
int size = s.length(), pos = 0;
if( size <= 1 )
return s;
Stack<String> result = new Stack<>();
while( pos < size )
{
char elem = s.charAt(pos);
if( elem == '[')
{
result.push("[");
}
else if( Character.isDigit(elem) )
{
int sum = elem - '0';
while( (pos + 1) < size && Character.isDigit(s.charAt(pos + 1)) )
{
sum = sum * 10 + (s.charAt(++pos) - '0');
}
result.push(String.valueOf(sum));
}
else if( elem == ']' )
{
StringBuilder partial = new StringBuilder();
//Append all the strings before the opening paranthesis.
while( !result.peek().equals("[")  )
{
//construct the partial string using the stack contents and count(Number of times a string should be repeated).
partial.insert(0, result.pop());
}
//pop "[".
result.pop();
// pop the count which indicates the number of times the partial string is to be repeated.
int count = Integer.parseInt(result.pop());
String repeat = partial.toString();
while( count-- > 1 )
{
partial.insert(0, repeat);
}
//push the intermediate back to stack.
result.push(partial.toString());
}
else
{
//Pushing the entire string inside the paranthesis or before start of another paranthesis.
int posStart = pos;
while( (pos + 1) < size && s.charAt(pos + 1) != ']' && !Character.isDigit(s.charAt(pos + 1)) )
pos++;
int posEnd = pos + 1;
// push the partial string to the stack.
result.push(s.substring(posStart, posEnd));
}
pos++;
}
StringBuilder output = new StringBuilder();
while( !result.isEmpty() )
{
output.insert(0, result.pop());
}
return output.toString();
}
}
``````

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