Question

Formatted question description: https://leetcode.ca/all/385.html

Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger.

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

Example 1:

Input: s = "324"
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.

Example 2:

Input: s = "[123,[456,[789]]]"
Output: [123,[456,[789]]]
Explanation: 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

Constraints:

1 <= s.length <= 5 * 10⁴
s consists of digits, square brackets "[]", negative sign '-', and commas ','.
s is the serialization of valid NestedInteger.
All the values in the input are in the range [-10⁶, 10⁶].

Algorithm

First judge whether s is empty, and return directly if it is empty.

If it is not empty, see if the first character is [,

If it is not, s is an integer, and we return the result directly.
If the first character is [,
- And the length of s is less than or equal to 2, indicating that there is no content, and the result is returned directly.
- On the other hand, if the length of s is greater than 2, we start traversing from i=1, we need a variable start to record the start position of a certain layer, and use cnt to record whether the actual position is the same depth, cnt=0 means Same depth.

Since each paragraph in the middle is separated by a comma, when we judge that cnt is 0, and the current character is a comma or has reached the end of the string, we take out the string between start and the current position to call the function recursively, Add the returned result to res, and then update start to i+1.

If you encounter [, the counter cnt increments by 1,
If encountering ], the counter cnt will decrement by 1

Code

import java.util.List;
import java.util.Stack;

public class Mini_Parser {

    class Solution_recursion {
        public NestedInteger deserialize(String s) {
            if (s.isEmpty()) return new NestedInteger();
            if (s.charAt(0) != '[') return new NestedInteger(Integer.valueOf(s));
            if (s.length() <= 2) return new NestedInteger(); // for cases, [[]] => []

            NestedInteger res = new NestedInteger();
            int start = 1; // 0 is `[`, skip it
            int bracketCount = 0;

            for (int i = 1; i < s.length(); ++i) {
                // s.charAt(i) == ',' => for when reaching ']' after '3' in eg. [11,[1,2,3],[4,5,6]]
                if (bracketCount == 0 && (s.charAt(i) == ',' || i == s.length() - 1)) {
                    res.add(deserialize(s.substring(start, i)));
                    start = i + 1;
                } 
                else if (s.charAt(i) == '[') ++bracketCount;
                else if (s.charAt(i) == ']') --bracketCount;
            }
            return res;
        }
    }

    class Solution {
        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()) { // if empty, then just continue pop from stack
                        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;
        }
    }


    // This is the interface that allows for creating nested lists.
    // You should not implement it, or speculate about its implementation
    class 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 false; };

        // @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() { return new Integer(1); }

        // 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() { return null; };
    }
}

############

/**
 * // 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 empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        if ("".equals(s)) {
            return new NestedInteger();
        }
        if (s.charAt(0) != '[') {
            return new NestedInteger(Integer.parseInt(s));
        }
        if (s.length() <= 2) {
            return new NestedInteger();
        }
        NestedInteger ans = new NestedInteger();
        int depth = 0;
        for (int i = 1, j = 1; i < s.length(); ++i) {
            if (depth == 0 && (s.charAt(i) == ',' || i == s.length() - 1)) {
                ans.add(deserialize(s.substring(j, i)));
                j = i + 1;
            } else if (s.charAt(i) == '[') {
                ++depth;
            } else if (s.charAt(i) == ']') {
                --depth;
            }
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/mini-parser/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    NestedInteger deserialize(string s) {
        if (s.empty()) return NestedInteger(); // empty list
        if (s[0] == '[') { // nested list
            NestedInteger n;
            int i = 1, end = s.size() - 1;
            while (i < end) {
                int begin = i;
                if (s[i] == '[') { // element being nested list
                    int cnt = 0;
                    do {
                        if (s[i] == '[') ++cnt;
                        else if (s[i] == ']') --cnt;
                        ++i;
                    } while (cnt > 0);
                } else {
                    while (isdigit(s[i]) || s[i] == '-') ++i;
                }
                n.add(deserialize(s.substr(begin, i - begin)));
                ++i;
            }
            return n;
        }
        // plain number
        return NestedInteger(stoi(s));
    }
};

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """
class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        if not s:
            return NestedInteger()
        if s[0] != '[':
            return NestedInteger(int(s))
        if len(s) <= 2: # '[]'
            return NestedInteger()
        ans = NestedInteger()
        depth, i = 0, 1 # i starting at 1, to skip first '['
        for j in range(1, len(s)):
            if depth == 0 and (s[j] == ',' or j == len(s) - 1):
                ans.add(self.deserialize(s[i:j])) # j at ']', exclusive
                i = j + 1
            elif s[j] == '[':
                depth += 1
            elif s[j] == ']':
                depth -= 1
        return ans

############

class Solution(object):
  def deserialize(self, s):
    """
    :type s: str
    :rtype: NestedInteger
    """

    def parse(s, i):
      if s[i] == "[":
        i += 1
        ret = NestedInteger()
        while i < len(s):
          if s[i] == "]":
            return ret, i + 1
          elif s[i] in "[-0123456789":
            res, i = parse(s, i)
            ret.add(res)
          else:
            i += 1
      else:
        j = i
        while j < len(s) and s[j] in "-0123456789":
          j += 1
        return NestedInteger(int(s[i:j])), j

    res, _ = parse(s, 0)
    return res

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (n NestedInteger) IsInteger() bool {}
 *
 * // Return the single integer that this NestedInteger holds, if it holds a single integer
 * // The result is undefined if this NestedInteger holds a nested list
 * // So before calling this method, you should have a check
 * func (n NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (n *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (n NestedInteger) GetList() []*NestedInteger {}
 */
func deserialize(s string) *NestedInteger {
	if s[0] != '[' {
		v, _ := strconv.Atoi(s)
		ans := NestedInteger{}
		ans.SetInteger(v)
		return &ans
	}
	stk := []*NestedInteger{}
	x := 0
	neg := false
	for i, c := range s {
		if c == '-' {
			neg = true
		} else if c >= '0' && c <= '9' {
			x = x*10 + int(c-'0')
		} else if c == '[' {
			stk = append(stk, &NestedInteger{})
		} else if c == ',' || c == ']' {
			if s[i-1] >= '0' && s[i-1] <= '9' {
				if neg {
					x = -x
				}
				t := NestedInteger{}
				t.SetInteger(x)
				stk[len(stk)-1].Add(t)
			}
			x = 0
			neg = false
			if c == ']' && len(stk) > 1 {
				t := stk[len(stk)-1]
				stk = stk[:len(stk)-1]
				stk[len(stk)-1].Add(*t)
			}
		}
	}
	return stk[0]
}

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *     If value is provided, then it holds a single integer
 *     Otherwise it holds an empty nested list
 *     constructor(value?: number) {
 *         ...
 *     };
 *
 *     Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     isInteger(): boolean {
 *         ...
 *     };
 *
 *     Return the single integer that this NestedInteger holds, if it holds a single integer
 *     Return null if this NestedInteger holds a nested list
 *     getInteger(): number | null {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a single integer equal to value.
 *     setInteger(value: number) {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 *     add(elem: NestedInteger) {
 *         ...
 *     };
 *
 *     Return the nested list that this NestedInteger holds,
 *     or an empty list if this NestedInteger holds a single integer
 *     getList(): NestedInteger[] {
 *         ...
 *     };
 * };
 */

function deserialize(s: string): NestedInteger {
    if (s[0] !== '[') {
        return new NestedInteger(+s);
    }
    const stk: NestedInteger[] = [];
    let x = 0;
    let neg = false;
    for (let i = 0; i < s.length; ++i) {
        if (s[i] === '-') {
            neg = true;
        } else if (s[i] === '[') {
            stk.push(new NestedInteger());
        } else if (s[i] >= '0' && s[i] <= '9') {
            x = x * 10 + s[i].charCodeAt(0) - '0'.charCodeAt(0);
        } else if (s[i] === ',' || s[i] === ']') {
            if (s[i - 1] >= '0' && s[i - 1] <= '9') {
                stk[stk.length - 1].add(new NestedInteger(neg ? -x : x));
            }
            x = 0;
            neg = false;
            if (s[i] === ']' && stk.length > 1) {
                const t = stk.pop()!;
                stk[stk.length - 1].add(t);
            }
        }
    }
    return stk[0];
}

385 - Mini Parser

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions