Medium

题目描述

给定一个字符串 s 表示一个嵌套列表的序列化，实现一个解析器来反序列化它并返回反序列化的 NestedInteger。

每个元素要么是一个整数，要么是一个列表，其元素也可能是整数或其他列表。

示例 1：

输入：s = "324"
输出：324
解释：你应该返回一个包含单个整数 324 的 NestedInteger 对象。

示例 2：

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

约束条件：

  • 1 <= s.length <= 5 * 10^4
  • s 由数字、方括号 “[]"、负号 ‘-’ 和逗号 ‘,’ 组成。
  • s 是有效 NestedInteger 的序列化。
  • 输入中的所有值都在范围 [-10^6, 10^6] 内。

解题思路

这道题目要求我们解析嵌套整数的字符串表示。我们需要处理两种情况：单个整数和包含多个元素的列表。

核心思路：

  1. 栈方法（推荐）：使用栈来处理嵌套结构。遇到 ‘[’ 时创建新的 NestedInteger 并入栈，遇到 ‘]’ 时出栈并将当前对象添加到栈顶的父对象中。

  2. 递归方法：使用递归来处理嵌套结构，需要维护当前解析位置的索引。

栈方法详解：

  • 使用栈存储正在构建的 NestedInteger 对象
  • 遇到 ‘[’ 时，创建新的空列表对象入栈
  • 遇到数字时，构建整数对象，如果栈不为空则添加到栈顶列表中
  • 遇到 ‘]’ 时，将栈顶对象出栈，如果栈仍不为空则将出栈对象添加到新的栈顶中
  • 遇到 ‘,’ 时继续处理下一个元素

这种方法能够很好地处理嵌套结构，时间复杂度为 O(n)，空间复杂度取决于嵌套的深度。

代码实现

class Solution {
public:
    NestedInteger deserialize(string s) {
        stack<NestedInteger> st;
        int i = 0;
        
        while (i < s.length()) {
            if (s[i] == '[') {
                st.push(NestedInteger());
                i++;
            } else if (s[i] == ']') {
                NestedInteger top = st.top();
                st.pop();
                if (!st.empty()) {
                    st.top().add(top);
                } else {
                    return top;
                }
                i++;
            } else if (s[i] == ',') {
                i++;
            } else {
                // Parse number
                int start = i;
                if (s[i] == '-') i++;
                while (i < s.length() && isdigit(s[i])) i++;
                int num = stoi(s.substr(start, i - start));
                NestedInteger ni(num);
                
                if (!st.empty()) {
                    st.top().add(ni);
                } else {
                    return ni;
                }
            }
        }
        
        return st.top();
    }
};

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        stack = []
        i = 0
        
        while i < len(s):
            if s[i] == '[':
                stack.append(NestedInteger())
                i += 1
            elif s[i] == ']':
                top = stack.pop()
                if stack:
                    stack[-1].add(top)
                else:
                    return top
                i += 1
            elif s[i] == ',':
                i += 1
            else:
                # Parse number
                start = i
                if s[i] == '-':
                    i += 1
                while i < len(s) and s[i].isdigit():
                    i += 1
                num = int(s[start:i])
                ni = NestedInteger(num)
                
                if stack:
                    stack[-1].add(ni)
                else:
                    return ni
        
        return stack[-1]

public class Solution {
    public NestedInteger Deserialize(string s) {
        Stack<NestedInteger> stack = new Stack<NestedInteger>();
        int i = 0;
        
        while (i < s.Length) {
            if (s[i] == '[') {
                stack.Push(new NestedInteger());
                i++;
            } else if (s[i] == ']') {
                NestedInteger top = stack.Pop();
                if (stack.Count > 0) {
                    stack.Peek().Add(top);
                } else {
                    return top;
                }
                i++;
            } else if (s[i] == ',') {
                i++;
            } else {
                // Parse number
                int start = i;
                if (s[i] == '-') i++;
                while (i < s.Length && char.IsDigit(s[i])) i++;
                int num = int.Parse(s.Substring(start, i - start));
                NestedInteger ni = new NestedInteger(num);
                
                if (stack.Count > 0) {
                    stack.Peek().Add(ni);
                } else {
                    return ni;
                }
            }
        }
        
        return stack.Peek();
    }
}

var deserialize = function(s) {
    const stack = [];
    let i = 0;
    
    while (i < s.length) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n 为字符串长度，需要遍历整个字符串一次
空间复杂度O(d)d 为嵌套的最大深度，栈的空间消耗

相关题目