385.Mini Parser

Tags: [recursion], [stack]

Link: https://leetcode.com/problems/mini-parser/#/description

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.

Solution: Recursion, Stack

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    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(object):
    def deserialize(self, s):
        """
        :type s: str
        :rtype: NestedInteger
        """

        if not s:
            return None

        return self.deserialize_helper(s, 0, len(s) - 1)

    def deserialize_helper(self, s, start, end):
        # base case
        if start > end or start >= len(s) or end < 0:
            return None

        if s[start] == '[' and s[end] == ']' and start + 1 == end:
            return NestedInteger()

        one_int = True
        for i in xrange(start, end + 1):
            if not ('0' <= s[i] <= '9' or s[i] == '-'):
                one_int = False
                break
        if one_int:
            return NestedInteger(self.build_int(s, start, end))

        if s[start] == '[' and s[end] == ']' and self.bucket_matched(s, start, end):
            start += 1
            end -= 1

        buff = []
        nested_int = NestedInteger()
        while start <= end:
            curr = s[start]
            if curr == '[':
                # find matched ']'
                stack = []
                matched_right_bucket_index = start
                while matched_right_bucket_index <= end:
                    c = s[matched_right_bucket_index]
                    if not stack or c == '[':
                        stack.append(matched_right_bucket_index)
                    elif c == ']':
                        stack.pop()
                        if not stack:
                            break
                    matched_right_bucket_index += 1

                if matched_right_bucket_index > end:
                    raise ValueError('The input is invalid')

                nested_int.add(self.deserialize_helper(s, start, matched_right_bucket_index))
                start = matched_right_bucket_index + 1
                continue

            elif '0' <= curr <= '9' or curr == '-':
                buff.append(curr)
            else:
                # curr == ',':
                if buff:
                    nested_int.add(NestedInteger(self.build_int(buff, 0, len(buff) - 1)))
                    buff = []

            start += 1

        if buff:
            nested_int.add(NestedInteger(self.build_int(buff, 0, len(buff) - 1)))

        return nested_int

    @staticmethod
    def build_int(digit_arr, start, end):
        if start > end:
            return None

        flag = 1
        if digit_arr[0] == '-':
            flag = -1
            start += 1

        return flag * int(''.join(digit_arr[start:end + 1]))

    @staticmethod
    def bucket_matched(s, left, right):
        if not s or left >= right or s[left] != '[' or s[right] != ']' :
            return False

        stack = []
        while left <= right:
            curr = s[left]
            if not stack or curr == '[':
                stack.append(left)
            elif curr == ']':
                stack.pop()
                if not stack:
                    return left == right
            left += 1

        return False

Revelation:

• Each time, when we want to remove the left and right buckets, we should first find the real matched corresponding right bucket based on the given left bucket.
• The depth of the recursion depends on the deep of the nested buckets.

Note:

• Time complexity = O(n), n is the length of the given string. Each char of the string only be accessed once.