Simple Java using single stack


  • 1
    S

    Decode string using a sinlge stack. Simply push the calculated bracket into the stack again.

    public String decodeString(String s) {
    		Stack<String> stk = new Stack<>();
    		for (int i = 0; i < s.length(); i++) {
    			if (s.charAt(i) == ']') {
    				String temp = "";
    				StringBuilder tempRepeat = new StringBuilder();
    				while (!stk.isEmpty() && !stk.peek().equals("[")) {
    					temp = stk.pop() + temp;
    				}
    				stk.pop();// pop ']'
    				int repeat = 0;
    				int pow = 0;
    				//finding the number by which the temp or [abc] needs to be repeated
    				while (!stk.isEmpty() && Character.isDigit(stk.peek().toCharArray()[0])) {
    					repeat = repeat + (int) Math.pow(10, pow) * (stk.pop().toCharArray()[0] - '0');
    					pow++;
    				}
    				//repeat temp or [abc]
    				for (int r = 0; r < repeat; r++) {
    					tempRepeat.append(temp);
    				}
    				//push result into stack
    				stk.push(tempRepeat.toString());
    			} else {
    				stk.push(s.charAt(i) + "");
    			}
    		}
    		String res = "";
    		while (!stk.isEmpty()) {
    			res = stk.pop() + res;
    		}
    		return res;
    	}
    

Log in to reply
 

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