Share my tree based thinking & Java code for NestedInteger problem

  • 0

    I am not a big fan of tricky if-else statement for string related parsing problem because it always messes me up. The idea I have for this problem is to use a stack and think the nested structure is a tree, for example:
    "[123,[[456,234],[789], 678], 234]"
    We split the whole string by delimiter ",", then iterate each string in the array. Start by parsing the string and know how many left brackets you have, and how many right brackets you have, and what's the integer within it (there is a chance no such integer exists, for example "[[]]", we will deal with that). The tree is a tree of NestedInteger (I will use list to represent such NestedInteger is a list, and use integer to represent such NestedInteger is an Integer) would look like this:
    list->(left child integer 123, middle child list -> (left child list -> (left child integer 456, right child integer 234), middle child list -> (single child integer 789), right child integer 678), right child integer 234)
    So algorithmically how do we do that? We start with an empty stack. Every time we parse a string, we push the number of NestedInteger into the stack and decrements the number of left brackets until it's 0. For every push if the stack is not empty then we let top of stack add the current NestedInteger into its list. When we're done with the pushing, if there is an Integer from the string, we let top of stack add the NestedInteger (which is just an Integer) into its list. Now we pop the stack for the number of right brackets. But we need to be cautious when we're parsing the last string, we want to keep one NestedInteger in the stack to return.
    See the code below:

    public NestedInteger deserialize(String s) {
        if (s == null || s.length() == 0) return null;
        if (s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
        String[] strs = s.split(",");
        Stack<NestedInteger> stack = new Stack<>();
        int len = strs.length;
        for (int i = 0; i < len; i++) {
            int[] parsed = parseString(strs[i]);
            while (parsed[0] > 0) {
                NestedInteger list = new NestedInteger();
                if (!stack.isEmpty()) {
            if (parsed.length == 3) stack.peek().add(new NestedInteger(parsed[2]));
            if (i + 1 < len) {
                while (parsed[1] > 0) {
            else {
                while (parsed[1] > 1) {
        return stack.peek();
    private int[] parseString(String s) {
        int len = s.length();
        int leftPt = 0;
        int rightPt = len - 1;
        while (leftPt < len && s.charAt(leftPt) == '[') leftPt++;
        while (rightPt >= 0 && s.charAt(rightPt) == ']') rightPt--;
        if (leftPt >= rightPt + 1) return new int[]{leftPt, len - 1 - rightPt};
        else return new int[]{leftPt, len - 1 - rightPt, Integer.parseInt(s.substring(leftPt, rightPt + 1))};

Log in to reply

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