385 Mini Parser

385. Mini Parser

1. Question

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

• String is non-empty.

• String does not contain white spaces.

• String contains only digits0-9,[,-,,].

Example 1:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
     a. An integer containing value 789.

2. Implementation

(1) Recursion

思路: 括号中的string相当于一个subproblem，所以当我们遇到左括号，可以递归地调用原来的方程，遇到右括号时，则跳出递归。总得思路其实和LC 224类似。

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    int i = 1;
    public NestedInteger deserialize(String s) {
        if (!s.startsWith("[")) {
            return new NestedInteger(Integer.parseInt(s));
        }

        return recDeserialize(s.toCharArray());
    }

    public NestedInteger recDeserialize(char[] s) {
        NestedInteger res = new NestedInteger();
        int n = s.length;

        while (i < n) {
            char c = s[i];
            if (c == '[') {
                ++i;
                res.add(recDeserialize(s));
            } 
            else if (c == ']') {
                ++i;
                break;
            }
            else if (c == ',') {
                ++i;
            }
            else {
                int sign = 1;
                int val = 0;

                if (c == '-') {
                    sign = -1;
                    ++i;
                }

                while (i < n && Character.isDigit(s[i])) {
                    val = 10 * val + s[i] - '0';
                    ++i;
                }
                res.add(new NestedInteger(sign * val));
            }
        }
        return res;
    }
}

(2) Stack

既然可以用递归，就可以用stack模拟递归的过程，总体思路和递归一样，只是遇到左括号时，将结果入栈，遇到右括号时出栈而已

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    // int i = 1;
    public NestedInteger deserialize(String s) {
        if (!s.startsWith("[")) {
            return new NestedInteger(Integer.parseInt(s));
        }

        // Method 1: Stack
        int n = s.length();

        Stack<NestedInteger> stack = new Stack();
        stack.push(new NestedInteger());

        // Start at index 1, since we know s starts with "["
        int i = 1;
        while (i < n - 1) {
            char c = s.charAt(i);

            if (c == '[') {
                stack.push(new NestedInteger());
                ++i;
            }
            else if (c == ']') {
                NestedInteger curNI = stack.pop();
                stack.peek().add(curNI);
                ++i;
            }
            else if (c == ',') {
                ++i;
            }
            else {
                int sign = 1;
                int val = 0;

                if (c == '-') {
                    sign = -1;
                    ++i;
                }

                while (i < n && Character.isDigit(s.charAt(i))) {
                    val = 10 * val + s.charAt(i) - '0';
                    ++i;
                }
                stack.peek().add(new NestedInteger(sign * val));
            }
        }
        return stack.pop();
    }
}

3. Time & Space Complexity

(1) Recursion: 时间复杂度O(n), 空间复杂度O(n)

(2) Stack: 时间复杂度O(n), 空间复杂度O(n)