---
title: 394. Decode String
tags: Stack
description: share source code.
---

# 394. Decode String

// used Stack to find [ as a starting point and ] as a end point
class Solution {
    public String decodeString(String s) {
        Stack<String> sk = new Stack<>();
        
        for(char ch : s.toCharArray()){
            // start with [
            if(ch == ']'){
                StringBuilder sb = new StringBuilder();
                // if not reach ] continue to pop 
                while(!sk.peek().equals("[")){
                    // insert front
                    sb.insert(0, sk.pop());
                }
                sk.pop(); // [
         
                int num = 0;
                int base = 1;
                // caculate the times to add the repeated word
                while(!sk.isEmpty() && Character.isDigit(sk.peek().charAt(0))){
                    num = num + (sk.pop().charAt(0) - '0')* base;
                    base *=10;
                }

                for(int i = 0; i < num; i++){
                    sk.push(sb.toString());
                }
            }else{
               sk.push(ch + ""); 
            } 
        }
        
        StringBuilder output = new StringBuilder();
        while(!sk.isEmpty()){
            output.insert(0, sk.pop());
        }

        return output.toString();
    }
}