1038. Parse Nested Text
A configuration tool stores structured numbers as compact text. The text s is either a single integer such as -42, or a bracketed list such as [7,[],[3,-8]] whose elements are separated by commas and are again integers or bracketed lists. There are no spaces anywhere in s.
Turn s into the matching NestedInteger: a plain integer for a number, or a list-type NestedInteger whose elements are built the same way, in the same order. Empty brackets give an empty list. The text is always well formed.
Read the text once from left to right, in O(n) time, and avoid recursion that could be as deep as the nesting.
Example 1
- Input:
- s = "-12"
- Output:
- -12
- Explanation:
The whole text is one number, so the result is the single integer -12.
Example 2
- Input:
- s = "[5,[],[7,-8]]"
- Output:
- [5,[],[7,-8]]
- Explanation:
The top list has three elements: the integer 5, an empty list, and a list holding 7 and -8.
Example 3
- Input:
- s = "[[3],[[4]]]"
- Output:
- [[3],[[4]]]
- Explanation:
Two sub-lists: one holding 3, and one holding a list that holds 4.
Constraints
1 ≤ length of s ≤ 105.
The nesting depth is at most 400.
s contains only digits, '-', ',', '[' and ']'.
-106 ≤ each integer ≤ 106.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(d)