Simple Java Solution using Stack


  • 52
    S
    public class Solution {
        public String decodeString(String s) {
            String res = "";
            Stack<Integer> countStack = new Stack<>();
            Stack<String> resStack = new Stack<>();
            int idx = 0;
            while (idx < s.length()) {
                if (Character.isDigit(s.charAt(idx))) {
                    int count = 0;
                    while (Character.isDigit(s.charAt(idx))) {
                        count = 10 * count + (s.charAt(idx) - '0');
                        idx++;
                    }
                    countStack.push(count);
                }
                else if (s.charAt(idx) == '[') {
                    resStack.push(res);
                    res = "";
                    idx++;
                }
                else if (s.charAt(idx) == ']') {
                    StringBuilder temp = new StringBuilder (resStack.pop());
                    int repeatTimes = countStack.pop();
                    for (int i = 0; i < repeatTimes; i++) {
                        temp.append(res);
                    }
                    res = temp.toString();
                    idx++;
                }
                else {
                    res += s.charAt(idx++);
                }
            }
            return res;
        }
    }

  • 8
    B

    There will be many temporary String object there. So I used a Stack with StringBuilder.

    class StrItem {
        int num = 0;
        StringBuilder sb = new StringBuilder();
        
        StrItem(int n) {this.num = n;}
    }
    
    public class Solution {
        public String decodeString(String s) {
            int num = 0;
            Stack<StrItem> stack = new Stack<>();
            stack.push(new StrItem(1));
            for (char c: s.toCharArray())
                switch (c) {
                    case '0': case '1': case '2': case '3': case '4':
                    case '5': case '6': case '7': case '8': case '9':
                        num = num * 10 + c - '0';
                        break;
                    case '[':
                        stack.push(new StrItem(num));
                        num = 0;
                        break;
                    case ']':
                        String curStr = stack.peek().sb.toString();
                        int n = stack.pop().num;
                        for (int i = 0; i < n; i++)
                            stack.peek().sb.append(curStr);
                        break;
                    default:
                        stack.peek().sb.append(c);
                }
            return stack.pop().sb.toString();
        }
    }
    

  • 121
    I

    @sampsonchan

            Stack<Integer> intStack = new Stack<>();
            Stack<StringBuilder> strStack = new Stack<>();
            StringBuilder cur = new StringBuilder();
            int k = 0;
            for (char ch : s.toCharArray()) {
                if (Character.isDigit(ch)) {
                    k = k * 10 + ch - '0';
                } else if ( ch == '[') {
                    intStack.push(k);
                    strStack.push(cur);
                    cur = new StringBuilder();
                    k = 0;
                } else if (ch == ']') {
                    StringBuilder tmp = cur;
                    cur = strStack.pop();
                    for (k = intStack.pop(); k > 0; --k) cur.append(tmp);
                } else cur.append(ch);
            }
            return cur.toString();
    

  • 0
    U
    This post is deleted!

  • 0
    T

    @iambright Thank you buddy, this solution is really awsome!


  • 1
    Q

    Easy understand java code

        public String decodeString(String s) {
            Stack<String> st = new Stack<>();
            String res = "";
            for(int i=0;i<s.length();i++) {
                int start = i;
                while(s.charAt(i)>='0' && s.charAt(i)<='9') i++;
                if(start!=i) st.push(s.substring(start, i));
                switch (s.charAt(i)) {
                    case '[':
                        st.push("[");
                        break;
                    case ']':
                        popString(st);
                        break;
                    default:
                        st.push(s.substring(i, i+1));
                }
            }
            while(!st.empty()) {
                res = st.pop() + res;
            }
            return res;
        }
        
        public void popString(Stack<String > st) {
            if(!st.empty()) {
                String tail = "";
                while(!st.peek().equals("[")) tail = st.pop() + tail;
                st.pop();
                int k = Integer.valueOf(st.pop());
                String res = "";
                while(k-->0) res += tail;
                st.push(res);
            }
        }
    

  • 1
    P

    Modified 3ms version :

            public  String decodeString(String s) { // O(n) space and time.
    		if (s.length() == 0)
    			return "";
    
    		Stack<String> chars = new Stack<>();
    		Stack<Integer> count = new Stack<>();
    		int num = 0;
    		for (int i = 0; i < s.length(); i++) {
    			char ch = s.charAt(i);
    			if (ch >= '0' && ch <= '9') { // is digit ?
    				num = num * 10 + ch - '0';
    				continue;
    			}
    			if (num > 0) {
    				count.push(num);
    				num = 0;
    			}
    
    			if (ch == ']') {
    				int times = count.pop();
    				StringBuilder strb = new StringBuilder();
    				String ch1 = chars.pop();
    				while (!ch1.equals("[")) { // pop until this bracket string is fetched.
    					strb.insert(0, ch1); // last in first out.
    					ch1 = chars.pop(); // will eventually pop '[' as well.
    				}
    				String str = strb.toString();
    				while (times-- > 1) // append that string appropriate times.
    					strb.append(str);
    				chars.push(strb.toString());
    
    			} else
    				chars.push(String.valueOf(ch));
    		}
    		StringBuilder strb = new StringBuilder();
    		while (!chars.isEmpty()) {
    			strb.insert(0, chars.pop());
    		}
    
    		return strb.toString();
    	}
    

  • 0
    J

    @sampsonchan Brilliant solution, but I'm wondering if toCharArray loops through the String unnecessarily to create the array. Would you be better off with a plain-old while or for loop?


  • 0
    D

    @sampsonchan Title would be better to change to "Simple Java Solution using Stacks" as the solution uses two Stacks.


  • 0

    similar solution, with regexps also:

    import java.util.regex.*;
    import java.util.Collection;
    import static java.util.stream.Collectors.joining;
    
    public class Solution {
        static final Pattern p = Pattern.compile("(\\d+)|([a-z]+)|(\\])");
        public String decodeString(String s) {
            Deque<Object> stack = new ArrayDeque<>();
            for (Matcher m = p.matcher(s); m.find(); )
                     if (m.group(1) != null) stack.addLast(Integer.parseInt(m.group(1)));
                else if (m.group(2) != null) stack.addLast(m.group(2));
                else if (m.group(3) != null) {
                    String groups = concat(stack);
                    int count = (Integer) stack.removeLast();
                    stack.addLast(repeat(groups, count));
                }
            return join(stack);
        }
        String concat(Deque<Object> stack) {
            LinkedList<String> groups = new LinkedList<>();
            while (!stack.isEmpty() && stack.peekLast() instanceof String)
                groups.addFirst((String) stack.removeLast());
            return join(groups);
        }
        String repeat(String str, int count) { return join(Collections.nCopies(count, str)); }
        String join(Collection<?> values) { return values.stream().map(Object::toString).collect(joining("")); }
    }
    

    or a shorter one:

    import java.util.regex.*;
    import java.util.Collection;
    
    public class Solution {
        final Pattern p = Pattern.compile("(\\d+)\\[([a-z]+)\\]"); 
        public String decodeString(String s) {
            StringBuilder results = new StringBuilder(s);
            for (Matcher m = p.matcher(results); m.find(); m.reset()) {
                String repeated = String.join("", Collections.nCopies(Integer.parseInt(m.group(1)), m.group(2)));
                results.replace(m.start(), m.end(), repeated);
            }
            return results.toString();
        }
    }
    

  • 0
    Y
    This post is deleted!

  • 0
    E

    Good solution!
    Seems if there's a test case like [ab] or 2[a[bc]] would fail, so I suggest adding a
    int like "leftCount"; and in the '[' case, add these two lines:

    leftCount++;
    if (countStack.size() < leftCount) countStack.push(0);


  • 0
    C

    @iaming Thx for sharing your code.


  • 0
    W
    This post is deleted!

Log in to reply
 

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