文章目录
题目
给定一个字符串 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 * 104
s 由数字、方括号 “[]”、负号 ‘-’ 、逗号 ','组成
用例保证 s 是可解析的 NestedInteger
输入中的所有值的范围是 [-106, 106]
答案
方法一：深度优先搜索
思路
根据题意，一个NestedInteger 实例只能包含下列两部分之一：1）一个整数；2）一个列表，列表中的每个元素都是一个 NestedInteger 实例。据此，NestedInteger 是通过递归定义的，因此也可以用递归的方式来解析。
从左至右遍历 s，
如果第一位是 ‘[’ 字符，则表示待解析的是一个列表，从 ‘[’ 后面的字符开始又是一个新的 NestedInteger 实例，我们仍调用解析函数来解析列表的元素，调用结束后如果遇到的是 , 字符，表示列表仍有其他元素，需要继续调用。如果是 ‘]’ 字符，表示这个列表已经解析完毕，可以返回 NestedInteger 实例。
否则，则表示待解析的 NestedInteger 只包含一个整数。我们可以从左至右解析这个整数，并注意是否是负数，直到遍历完或者遇到非数字字符（ ‘]’ 或 ‘,’），并返回 NestedInteger 实例。
代码
class Solution { int index = 0; public NestedInteger deserialize(String s) { if (s.charAt(index) == '[') { index++; NestedInteger ni = new NestedInteger(); while (s.charAt(index) != ']') { ni.add(deserialize(s)); if (s.charAt(index) == ',') { index++; } } index++; return ni; } else { boolean negative = false; if (s.charAt(index) == '-') { negative = true; index++; } int num = 0; while (index < s.length() && Character.isDigit(s.charAt(index))) { num = num * 10 + s.charAt(index) - '0'; index++; } if (negative) { num *= -1; } return new NestedInteger(num); } } }
复杂度分析
时间复杂度：O(n)，其中 n 是 s 的长度。我们需要遍历 s 的每一位来解析。
空间复杂度：O(n)，其中 n 是 s 的长度。深度优先搜索的深度最多为 O(n)，需要 O(n) 的栈空间。
方法二：栈
思路
上述递归的思路也可以用栈来模拟。从左至右遍历 ss，如果遇到 ‘[’，则表示是一个新的 NestedInteger 实例，需要将其入栈。如果遇到 ‘]’ 或 ‘,’，则表示是一个数字或者 NestedInteger 实例的结束，需要将其添加入栈顶的 NestedInteger 实例。最后需返回栈顶的实例。
代码
class Solution { public NestedInteger deserialize(String s) { if (s.charAt(0) != '[') { return new NestedInteger(Integer.parseInt(s)); } Deque<NestedInteger> stack = new ArrayDeque<NestedInteger>(); int num = 0; boolean negative = false; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '-') { negative = true; } else if (Character.isDigit(c)) { num = num * 10 + c - '0'; } else if (c == '[') { stack.push(new NestedInteger()); } else if (c == ',' || c == ']') { if (Character.isDigit(s.charAt(i - 1))) { if (negative) { num *= -1; } stack.peek().add(new NestedInteger(num)); } num = 0; negative = false; if (c == ']' && stack.size() > 1) { NestedInteger ni = stack.pop(); stack.peek().add(ni); } } } return stack.pop(); } }
复杂度分析
时间复杂度：O(n)，其中 n 是 s 的长度。我们需要遍历 s 的每一位来解析。
空间复杂度：O(n)，其中 n 是 s 的长度。栈的深度最多为 O(n)。
