Skip to content

Latest commit

 

History

History
177 lines (135 loc) · 4.92 KB

385.mini-parser.md

File metadata and controls

177 lines (135 loc) · 4.92 KB
Raw

题目地址(385. 迷你语法分析器)

https://leetcode-cn.com/problems/mini-parser/

题目描述

给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。

列表中的每个元素只可能是整数或整数嵌套列表

提示：你可以假定这些字符串都是格式良好的：

字符串非空
字符串不包含空格
字符串只包含数字0-9、[、-、,、]

 

示例 1：

给定 s = "324",

你应该返回一个 NestedInteger 对象，其中只包含整数值 324。


示例 2：

给定 s = "[123,[456,[789]]]",

返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：

1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表：
    i.  一个 integer 包含值 456
    ii. 一个包含一个元素的嵌套列表
         a. 一个 integer 包含值 789

前置知识

  • 栈
  • 递归

公司

  • 暂无

思路

我们可以直接使用 eval 来将字符串转化为数组。

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        def dfs(cur):
            if type(cur) == int:
                return NestedInteger(cur)
            ans = NestedInteger()
            for nxt in cur:
                ans.add(dfs(nxt))
            return ans

        return dfs(eval(s))

接下来，我们考虑如何实现 eval。

这其实是一个简单的栈 + dfs 题目。力扣中有非常多的题目都使用了这个题目，比如一些编码解码的题目，eg：394. 字符串解码。

关键点

  • 栈+递归。遇到 [ 开启新的递归，遇到 ] 返回

代码

  • 语言支持：Python3

Python3 Code:

# """
# 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:
        def dfs(cur):
            if type(cur) == int:
                return NestedInteger(cur)
            ans = NestedInteger()
            for nxt in cur:
                ans.add(dfs(nxt))
            return ans
        def to_array(i):
            stack = []
            num = ''
            while i < len(s):
                if s[i] == ' ':
                    i += 1
                    continue
                elif s[i] == ',':
                    if num:
                        stack.append(int(num or '0'))
                        num = ''
                elif s[i] == '[':
                    j, t = to_array(i+1)
                    stack.append(t)
                    i = j
                elif s[i] == ']':
                    break
                else:
                    num += s[i]
                i += 1
            if num:
                stack.append(int(num))
            return i, stack
        return dfs(to_array(0)[1][0])

复杂度分析

令 n 为 s 长度。

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。