385. 迷你语法分析器

🟠   🔖  栈 深度优先搜索 字符串  🔗 力扣 LeetCode

题目

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^4
• 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^6, 10^6].

题目大意

给定一个字符串 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^4
• s 由数字、方括号 "[]"、负号 '-' 、逗号 ','组成
• 用例保证 s 是可解析的 NestedInteger
• 输入中的所有值的范围是 [-10^6, 10^6]

解题思路

1. 解析字符串

   • 使用 JSON.parse() 将字符串解析为原生 JavaScript 数据结构（可能是数字或嵌套数组）。

2. 递归构建对象

   • 若当前节点是数字，直接构造 NestedInteger 并设置为该整数。
   • 若当前节点是数组，则创建新的 NestedInteger 并递归解析其子节点，依次添加到结果中。

3. 返回结果

   • 最终返回由递归构建出的 NestedInteger 对象。

复杂度分析

• 时间复杂度: O(n)，其中 n 为输入字符串解析成的数据结构的节点数量，遍历每个节点需要线性时间。

• 空间复杂度: O(d)，其中 d 是嵌套深度，由递归栈所决定。

代码

/**
 * @param {string} s
 * @return {NestedInteger}
 */
var deserialize = function (s) {
	if (!s) return null;

	const dfs = (data) => {
		const res = new NestedInteger();

		if (typeof data === 'number') {
			res.setInteger(data);
			return res;
		}

		for (let item of data) {
			res.add(dfs(item));
		}

		return res;
	};
	return dfs(JSON.parse(s));
};
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * function NestedInteger() {
 *
 *     Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     @return {boolean}
 *     this.isInteger = function() {
 *         ...
 *     };
 *
 *     Return the single integer that this NestedInteger holds, if it holds a single integer
 *     Return null if this NestedInteger holds a nested list
 *     @return {integer}
 *     this.getInteger = function() {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a single integer equal to value.
 *     @return {void}
 *     this.setInteger = function(value) {
 *         ...
 *     };
 *
 *     Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 *     @return {void}
 *     this.add = function(elem) {
 *         ...
 *     };
 *
 *     Return the nested list that this NestedInteger holds, if it holds a nested list
 *     Return null if this NestedInteger holds a single integer
 *     @return {NestedInteger[]}
 *     this.getList = function() {
 *         ...
 *     };
 * };
 */

相关题目

题号	标题	题解	标签	难度	力扣
341	扁平化嵌套列表迭代器	[✓]	栈 树 深度优先搜索 3+	🟠	🀄️ 🔗
439	三元表达式解析器 🔒		栈 递归 字符串	🟠	🀄️ 🔗
722	删除注释		数组 字符串	🟠	🀄️ 🔗