Input is a pre-order traversal, Java stack solution


  • 0
    D

    Input string is actually a pre-order traversal of a tree. For example, 2[a] means a tree. Root contains 2, and [ means go to children, a is what sub-tree contains, and ] means go back to root. So we can maintain a stack.

    public class Solution {
        public String decodeString(String s) {
            if (s == null || s.length() == 0) {
                return "";
            }
            s = "1[" + s + "]";
            Stack<TreeNode> stack = new Stack<>();
            Token token = new Token("", TokenType.NULL, -1);
            int repeat = 0;
            String ret = null;
            while ((token = findNextToken(s, token.eIndex + 1)) != null) {
                switch (token.type) {
                    case INTEGER:
                        repeat = token.number();
                        break;
                    case LEFTBRACKET:
                        stack.push(new TreeNode(repeat));
                        break;
                    case STRING:
                        assert stack.size() > 0;
                        stack.peek().buf.append(token.string());
                        break;
                    case RIGHTBRACKET:
                        assert stack.size() > 0;
                        TreeNode node = stack.pop();
                        StringBuffer sb = new StringBuffer();
                        String nodestr = node.buf.toString();
                        for (int i = 0; i < node.repeat; i++) {
                            sb.append(nodestr);
                        }
                        if (stack.size() > 0) {
                            stack.peek().buf.append(sb.toString());
                        } else {
                            ret = sb.toString();
                        }
                        break;
                    default:
                        assert false;
                }
            }
            return ret;
        }
        
        private Token findNextToken(String s, int pos) {
            if (pos >= s.length()) {
                return null;
            }
            char first = s.charAt(pos);
            if (Character.isDigit(first)) {
                int end = pos;
                for (; end < s.length() && Character.isDigit(s.charAt(end)); end++) {}
                return new Token(s.substring(pos, end), TokenType.INTEGER, end - 1);
            } else if (Character.isLetter(first)) {
                int end = pos;
                for (; end < s.length() && Character.isLetter(s.charAt(end)); end++) {}
                return new Token(s.substring(pos, end), TokenType.STRING, end - 1);
            } else if (first == '[') {
                return new Token("[", TokenType.LEFTBRACKET, pos);
            } else {
                assert first == ']';
                return new Token("]", TokenType.RIGHTBRACKET, pos);
            }
        }
        
        class Token {
            String str;
            TokenType type;
            int eIndex;
            
            public Token(String str, TokenType type, int eIndex) {
                this.str = str;
                this.type = type;
                this.eIndex = eIndex;
            }
            
            public int number() {
                return Integer.parseInt(str);
            }
            
            public String string() {
                return str;
            }
        }
        
        enum TokenType {
            INTEGER, LEFTBRACKET, STRING, RIGHTBRACKET, NULL
        }
        
        class TreeNode {
            int repeat;
            StringBuffer buf = new StringBuffer();
            
            public TreeNode(int repeat) {
                this.repeat = repeat;
            }
        }
    }
    

Log in to reply
 

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