Intuitive Java solution using stack with comments


  • 0

    I'm going for the most intuitive approach parsing char one by one. No recursion, no look ahead, just one stack. The code in Java may be a little long, but the idea is very clear. Here is the code for your reference.

        public NestedInteger deserialize(String s) {
            if (!s.contains("[")) return new NestedInteger(Integer.valueOf(s));
            
            Stack<NestedInteger> stack = new Stack<>();
            stack.push(new NestedInteger());        // Create outmost one, so iterate string [1,len-1]
            
            NestedInteger cur = null;
            for (int i = 0, sign = 1; i < s.length() - 1; i++) {
                char c = s.charAt(i);
                if (c == '[') {                     // '[': New list linked with stack top
                    NestedInteger list = new NestedInteger();
                    if (!stack.isEmpty()) {
                        stack.peek().add(list);
                    }
                    stack.push(list);
                } else if (c == '-') {
                    sign = -1;
                } else if ('0' <= c && c <= '9') {  // '0~9': Update cur number
                    if (cur == null) {
                        stack.peek().add(cur = new NestedInteger(0));
                    }
                    cur.setInteger(cur.getInteger() * 10 + sign * (c - '0'));
                } else {                            // ',' or ']': number and list ends
                    if (c == ']') {
                        stack.pop();
                    }
                    cur = null;
                    sign = 1;
                }
            }
            return stack.pop();
        }
    

  • 0

    u said // so iterate string [1,len-1]

    why in the for loop

    for (int i = 0, sign = 1; i < s.length() - 1; i++) 
    

    uses i=0 for the beginning?


Log in to reply
 

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