Iterative Java solution with explanation, 4ms


  • 0
    M

    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();
        }
    }
    

Log in to reply
 

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