What is the main challenge in Mini Parser?

The core challenge is correctly managing stack-based state to parse integers and nested lists while maintaining hierarchy.

Can Mini Parser handle negative integers?

Yes, the parser must detect negative signs and include them when constructing integer values.

How does the stack help in parsing nested lists?

The stack keeps track of the current NestedInteger context at each level, ensuring proper placement of nested elements.

What is the expected output for s = "[123,[456,[789]]]"?

A NestedInteger object containing two elements: integer 123 and a nested list [456,[789]] preserving the hierarchy.

Why is Mini Parser considered a stack-based state management problem?

Because parsing requires tracking multiple active nested lists and their elements simultaneously, which is naturally handled by a stack.

#385

Medium

auto_awesome栈·状态

LeetCode 题解工作台

迷你语法分析器

给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。列表中的每个元素只可能是整数或整数嵌套列表示例 1：输入： s = "324", 输出： 324 解释：你应该返回一个 NestedInteger 对象，其中只包含整数值 32…

字符串栈深度优先搜索

题目描述

给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。

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

示例 1：

输入：s = "324",
输出：324
解释：你应该返回一个 NestedInteger 对象，其中只包含整数值 324。

示例 2：

输入：s = "[123,[456,[789]]]",
输出：[123,[456,[789]]]
解释：返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：
1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表：
    i.  一个 integer 包含值 456
    ii. 一个包含一个元素的嵌套列表
         a. 一个 integer 包含值 789

提示：

1 <= s.length <= 5 * 10⁴
s 由数字、方括号 "[]"、负号 '-' 、逗号 ','组成
用例保证 s 是可解析的 NestedInteger
输入中的所有值的范围是 [-10⁶, 10⁶]

lightbulb

解题思路

方法一：递归

我们首先判断字符串 $s$ 是否为空或是一个空列表，如果是的话，直接返回一个空的 NestedInteger 即可。如果 $s$ 是一个整数，我们直接返回一个包含这个整数的 NestedInteger。否则，我们从左到右遍历字符串 $s$ ，如果当前深度为 $0$ ，并且遇到了逗号或者字符串 $s$ 的末尾，则我们截取出一个子串并递归调用函数解析该子串，将返回值加入到列表中。否则，如果当前遇到了左括号，我们将深度加 $1$ ，并继续遍历。如果遇到了右括号，我们将深度减 $1$ ，继续遍历。

遍历结束后，返回答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

# """
# 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 or s == '[]':
            return NestedInteger()
        if s[0] != '[':
            return NestedInteger(int(s))
        ans = NestedInteger()
        depth, j = 0, 1
        for i in range(1, len(s)):
            if depth == 0 and (s[i] == ',' or i == len(s) - 1):
                ans.add(self.deserialize(s[j:i]))
                j = i + 1
            elif s[i] == '[':
                depth += 1
            elif s[i] == ']':
                depth -= 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) where n is the length of the string, as each character is processed once. Space complexity is O(d) for the stack, where d is the maximum depth of nesting, to track active NestedInteger objects.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to manage multiple nesting levels without losing context.
question_mark
Watch if they correctly handle negative integers and multi-digit numbers.
question_mark
Check for proper stack use to maintain current parsing state.

warning

常见陷阱

外企场景

error
Failing to handle single integers outside brackets correctly.
error
Incorrectly appending integers to the wrong NestedInteger after closing a bracket.
error
Ignoring negative signs or multi-digit numbers when parsing integers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Parsing strings with additional whitespace or non-standard separators.
arrow_right_alt
Supporting optional null or empty lists within the nested structure.
arrow_right_alt
Handling extremely deep nesting requiring recursion or explicit stack management.

help

常见问题

外企场景

继续练习

#388 文件的最长绝对路径 #399 除法求值 #402 移掉 K 位数字