Java solution using stack


  • 1
    C
    public String decodeString(String s) {
            // this is required to track nested []
            Stack<Entry> stack = new Stack<Entry>();
        	stack.push(new Entry(1, new StringBuilder()));
        	
        	int idx = 0, val = 0;
        	while(idx < s.length()){
        		char ch = s.charAt(idx++);
        		
        		if(ch >= '0' && ch <= '9'){
        			val = (val * 10) + (int)(ch - '0');
        		}
        		// begining of a new subsection
        		else if(ch == '['){
        			stack.push(new Entry(val, new StringBuilder()));
        			val = 0;
        		}
        		// time to compute nexted subsection
        		else if (ch == ']'){
        			StringBuilder sb1 = new StringBuilder();
        			Entry top = stack.pop();
        			String str = top.sb.toString();
        			while(top.val > 0){
        				sb1.append(str);
        				top.val--;
        			}
        			
        			stack.peek().sb.append(sb1);
        		}
        		else{
        			stack.peek().sb.append(ch);
        		}
        	}
        	
        	// since its mentioned that input is correctly formatted so stack will always any atleast one entry
        	return stack.peek().sb.toString();
        }
        
        private static class Entry{
        	int val;
        	StringBuilder sb;
        	
        	public Entry(int val, StringBuilder sb){
        		this.val = val;
        		this.sb = sb;
        	}
        }
    

Log in to reply
 

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