Java solution using Stack and String Builder


  • 0
    H
    public String decodeString(String s) 
    	{	
    		if(s == null || s.length() == 0)
    			return s;
    		
    		int len = s.length();
            StringBuilder result = new StringBuilder();
            Stack<Character> stack = new Stack<Character>();
            stack.push(s.charAt(0));
            int i = 1;
            
            while(!stack.isEmpty() && i < len)
            {
            	char curChar = s.charAt(i);
            	if(curChar != ']')
            		stack.push(curChar);
            	else
            	{	
            		StringBuilder sequence = new StringBuilder();
            		while(stack.peek() != '[')
            		{
            			sequence.append(stack.pop());
            		}
            		//pop out the [ character
            		stack.pop();
            		//pop till we get numeric values and build the repetition number
            		int repetition = 0;
            		int power = 0;
            		while(!stack.isEmpty() && stack.peek() >= '0' && stack.peek() <= '9')
            		{
            			repetition += (stack.pop()-'0')*Math.pow(10, power);
            			power++;
            		}
            		
            		//form the repetition of the sequence string
            		String repeated = new String(new char[repetition]).replace("\0", sequence.toString());
            		//reverse the repeated string and put it back in the stack
            		repeated = new StringBuilder(repeated).reverse().toString();
            		for(int j = 0; j < repeated.length(); j++)
            				stack.push(repeated.charAt(j));
            	}
            	i++;
            }
            
            //pop all elements from the stack and append to the result
            for(char s1: stack)
            	result.append(s1);
            
            return result.toString();
        }
    

  • 1
    H

    Algorithm: Something similar to the technique used in balancing parentheses. Use a stack to push elements of

    • the string if they are not ]. If ], we need form the repetition. Start popping out elements till we get [
    • Once [ is got, we will have number before it, which will be the repetition of the string enclosed between [ and ]
    • Since it can be more than single digit number, keep popping till we get a numeric number. Once that is done,
    • we have the enclosed string and the repetition. Repeat the string that number of times and put back in the stack.
    • Important is that we reverse the repeated string before putting back in stack, since we pop elements from the end (LIFO).
    • In the end, the stack will contain the output string. Pop out all elements and form the result. bolded text

Log in to reply
 

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