An Java Iterative Solution


  • 48
    A

    This approach will just iterate through every char in the string (no recursion).

    • If encounters '[', push current NestedInteger to stack and start a new one.
    • If encounters ']', end current NestedInteger and pop a NestedInteger from stack to continue.
    • If encounters ',', append a new number to curr NestedInteger, if this comma is not right after a brackets.
    • Update index l and r, where l shall point to the start of a integer substring, while r shall points to the end+1 of substring.

    Java Code:

    public NestedInteger deserialize(String s) {
        if (s.isEmpty())
            return null;
        if (s.charAt(0) != '[') // ERROR: special case
            return new NestedInteger(Integer.valueOf(s));
            
        Stack<NestedInteger> stack = new Stack<>();
        NestedInteger curr = null;
        int l = 0; // l shall point to the start of a number substring; 
                   // r shall point to the end+1 of a number substring
        for (int r = 0; r < s.length(); r++) {
            char ch = s.charAt(r);
            if (ch == '[') {
                if (curr != null) {
                    stack.push(curr);
                }
                curr = new NestedInteger();
                l = r+1;
            } else if (ch == ']') {
                String num = s.substring(l, r);
                if (!num.isEmpty())
                    curr.add(new NestedInteger(Integer.valueOf(num)));
                if (!stack.isEmpty()) {
                    NestedInteger pop = stack.pop();
                    pop.add(curr);
                    curr = pop;
                }
                l = r+1;
            } else if (ch == ',') {
                if (s.charAt(r-1) != ']') {
                    String num = s.substring(l, r);
                    curr.add(new NestedInteger(Integer.valueOf(num)));
                }
                l = r+1;
            }
        }
        
        return curr;
    }

  • 48
    R
        public NestedInteger deserialize(String s) {
            if (!s.startsWith("[")) {
                return new NestedInteger(Integer.valueOf(s));
            }
            Stack<NestedInteger> stack = new Stack<>();
            NestedInteger res = new NestedInteger();
            stack.push(res);
            int start = 1;
            for (int i = 1; i < s.length(); i ++) {
                char c = s.charAt(i);
                if (c == '[') {
                    NestedInteger ni = new NestedInteger();
                    stack.peek().add(ni);
                    stack.push(ni);
                    start = i + 1;
                } else if (c == ',' || c == ']') {
                    if (i > start) {
                        Integer val = Integer.valueOf(s.substring(start, i));
                        stack.peek().add(new NestedInteger(val));
                    }
                    start = i + 1;
                    if (c == ']') {
                        stack.pop();
                    }
                } 
            }
            return res;
        }
    

  • 3
    F

    Actually instead of using substring() to parse the integer, we could iteratively construct the number. The other parts are the same.

    public class Solution {
        public NestedInteger deserialize(String s) {
            if (s.charAt(0) != '[') {
                return new NestedInteger(Integer.parseInt(s));
            }
            
            int num = 0;
            int sign = 1;
            boolean parsingNum = false;
            Deque<NestedInteger> stack = new ArrayDeque<>();
            NestedInteger curr = null;
            
            for (int i = 0; i < s.length(); ++i) {
                char c = s.charAt(i);
                
                if (Character.isDigit(c)) {
                    parsingNum = true;
                    num = num * 10 + sign * (c - '0');
                    
                } else if (c == '-') {
                    sign = -1;
                    parsingNum = true;
                    
                } else if (c == ',') {
                    if (parsingNum) {
                        curr.add(new NestedInteger(num));
                        parsingNum = false;
                        num = 0;
                        sign = 1;
                    }
                    
                } else if (c == '[') {
                    // so we have a new container from here
                    if (curr != null) {
                        stack.addFirst(curr);
                    }
                    curr = new NestedInteger();
                    
                } else if (c == ']') {
                    if (parsingNum) {
                        curr.add(new NestedInteger(num));
                        parsingNum = false;
                        num = 0;
                        sign = 1;
                    }
                    if (!stack.isEmpty()) {
                        stack.peekFirst().add(curr);
                        curr = stack.removeFirst();
                    }
                }
            }
            
            return curr;
        }
    }
    

  • 8
    M

    Thanks for sharing your answer! Here is my recursive version

    public class Solution {
        
        int i = 1;
        int start = i;
        
        public NestedInteger deserialize(String s) {
            if (s.charAt(0) != '[') return new NestedInteger(Integer.valueOf(s));
            NestedInteger res = new NestedInteger();
            while (i < s.length()) {
                char c = s.charAt(i);
                if (c == '[') {
                    start = ++i;
                    NestedInteger ni = deserialize(s);
                    res.add(ni);
                }
                else if (c == ']' || c == ',') {
                    String num = s.substring(start, i);
                    if (!num.equals("")) {
                        int n = Integer.valueOf(num);
                        NestedInteger ni = new NestedInteger(n);
                        res.add(ni);
                    }
                    start = ++i;
                    if (c == ']') break;
                } 
                else 
                    i++;
            }
            return res;
        }
        
    }
    

  • 0
    L

    @marcusgao94 wow, your solution is the best I've seen so far. I would give you a thousand upvotes if I could. 😘😘😘😘


  • 1
    C

    @marcusgao94 nice recursive solution


  • 0

    @fyears said in An Java Iterative Solution:

    true

    good solution, but I think there's also a method to solve this if you don't introduce 'parsingNum'.


  • 0
    Y

    @AlexTheGreat Nice solution! Easy to understand. Thanks. Could you and anybody else please analyze the time and space complexities? My thinking is the following:

    Time: iterate through the string: O(n), in each loop, there is substring method: O(n) in Java 7, so it turns out: O(n^2)

    Space: pretty confused..

    Please correct me if I am wrong. Thanks again.


  • 0
    C

    Thanks for sharing your thought. Here is my Python implementation.

    def deserialize(self, s):
        # '-1' is not digit
        if s and s[-1].isdigit():
            return int(s)
    
        nested_integer = None
        digits = ''
        stack = []
        for c in s:
            if c.isdigit() or c == '-':
                digits += c
            elif c == '[':
                if nested_integer:
                    stack.append(nested_integer)
                nested_integer = NestedInteger()
            elif c == ']':
                if digits:
                    nested_integer.add(NestedInteger(int(digits)))
                    digits = ''
                if stack:
                    previous_nested_integer = stack.pop()
                    previous_nested_integer.add(nested_integer)
                    nested_integer = previous_nested_integer
            elif c == ',':
                if digits:
                    nested_integer.add(NestedInteger(int(digits)))
                    digits = ''
    
        return nested_integer
    

  • 0
    Y

    Don't you think you used too much if...

    private NestedInteger root = null;
    private NestedInteger curRoot = null;
    private Stack<NestedInteger> stk = new Stack<>();
    
    public NestedInteger deserialize(String s) {
            if (null == s || s.length() == 0)           return new NestedInteger();
            if (s.length() != 0 && s.charAt(0) != '[')  return new NestedInteger(Integer.valueOf(s));
    
            int len = s.length();
            for (int i = 0; i < len; ++i) {
                switch (s.charAt(i)) {
                    case '[':
                        NestedInteger newNode = new NestedInteger();
                        if (root == null) {
                            root = newNode;
                            stk.push(newNode);
                            continue;
                        }
                        curRoot = stk.peek();
                        curRoot.add(newNode);
                        stk.push(newNode);
                        break;
    
                    case ']':
                        stk.pop();
                        break;
    
                    case ',': case ' ': // ignore
                        break;
    
                    default:           // number
                        int st = i;
                        while (s.charAt(i) == '-' || Character.isDigit(s.charAt(i))) ++i;
                        // ignore, emtpy~
                        if (i == st) continue;
    
                        String v = s.substring(st, i);
                        curRoot = stk.peek();
                        curRoot.add(new NestedInteger(Integer.valueOf(v)));
                        i -= 1; //because there is a i++ in the for loop
                        break;
                }
            }
            return root;
        }
    

  • 0
    K

    The same as I think, but i do not know how to implement NestedInteger


Log in to reply
 

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