Problem

Given a string str, return parsed JSON parsedStr. You may assume the str is a valid JSON string hence it only includes strings, numbers, arrays, objects, booleans, and null. str will not include invisible characters and escape characters.

Please solve it without using the built-in JSON.parse method.

Examples

Example 1:

1
2
3

Input: str = '{"a":2,"b":[1,2,3]}'
Output: {"a":2,"b":[1,2,3]}
Explanation:  Returns the object represented by the JSON string.

Example 2:

1
2
3

Input: str = 'true'
Output: true
Explanation: Primitive types are valid JSON.

Example 3:

1
2
3

Input: str = '[1,5,"false",{"a":2}]'
Output: [1,5,"false",{"a":2}]
Explanation: Returns the array represented by the JSON string.

Constraints:

  • str is a valid JSON string
  • 1 <= str.length <= 10^5

Solution

Method 1 – Recursive Descent Parsing 1

Intuition

To parse a JSON string without using JSON.parse, we can implement a recursive descent parser. The parser reads the string character by character, handling objects, arrays, strings, numbers, booleans, and null according to JSON syntax rules.

Approach

  1. Use a pointer/index to track the current position in the string.
  2. Define a recursive function to parse the value at the current position:
    • If the current character is ‘"’, parse a string.
    • If the current character is a digit or ‘-’, parse a number.
    • If the current character is ‘{’, parse an object by recursively parsing key-value pairs.
    • If the current character is ‘[’, parse an array by recursively parsing elements.
    • If the current character starts with ’t’, ‘f’, or ’n’, parse true, false, or null.
  3. Skip whitespace (not needed here as per constraints).
  4. Return the parsed value.

Code

 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

class Solution {
    parse(str) {
        let i = 0;
        function parseValue() {
            if (str[i] === '"') return parseString();
            if (str[i] === '-' || (str[i] >= '0' && str[i] <= '9')) return parseNumber();
            if (str[i] === '{') return parseObject();
            if (str[i] === '[') return parseArray();
            if (str.startsWith('true', i)) { i += 4; return true; }
            if (str.startsWith('false', i)) { i += 5; return false; }
            if (str.startsWith('null', i)) { i += 4; return null; }
        }
        function parseString() {
            let res = '';
            i++; // skip initial '"'
            while (str[i] !== '"') res += str[i++];
            i++; // skip closing '"'
            return res;
        }
        function parseNumber() {
            let start = i;
            if (str[i] === '-') i++;
            while (str[i] >= '0' && str[i] <= '9') i++;
            if (str[i] === '.') {
                i++;
                while (str[i] >= '0' && str[i] <= '9') i++;
            }
            return Number(str.slice(start, i));
        }
        function parseArray() {
            let arr = [];
            i++; // skip '['
            if (str[i] === ']') { i++; return arr; }
            while (true) {
                arr.push(parseValue());
                if (str[i] === ',') i++;
                else if (str[i] === ']') { i++; break; }
            }
            return arr;
        }
        function parseObject() {
            let obj = {};
            i++; // skip '{'
            if (str[i] === '}') { i++; return obj; }
            while (true) {
                let key = parseString();
                i++; // skip ':'
                obj[key] = parseValue();
                if (str[i] === ',') i++;
                else if (str[i] === '}') { i++; break; }
            }
            return obj;
        }
        return parseValue();
    }
}
 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

class Solution {
    parse(str: string): any {
        let i = 0;
        function parseValue(): any {
            if (str[i] === '"') return parseString();
            if (str[i] === '-' || (str[i] >= '0' && str[i] <= '9')) return parseNumber();
            if (str[i] === '{') return parseObject();
            if (str[i] === '[') return parseArray();
            if (str.startsWith('true', i)) { i += 4; return true; }
            if (str.startsWith('false', i)) { i += 5; return false; }
            if (str.startsWith('null', i)) { i += 4; return null; }
        }
        function parseString(): string {
            let res = '';
            i++;
            while (str[i] !== '"') res += str[i++];
            i++;
            return res;
        }
        function parseNumber(): number {
            let start = i;
            if (str[i] === '-') i++;
            while (str[i] >= '0' && str[i] <= '9') i++;
            if (str[i] === '.') {
                i++;
                while (str[i] >= '0' && str[i] <= '9') i++;
            }
            return Number(str.slice(start, i));
        }
        function parseArray(): any[] {
            let arr: any[] = [];
            i++;
            if (str[i] === ']') { i++; return arr; }
            while (true) {
                arr.push(parseValue());
                if (str[i] === ',') i++;
                else if (str[i] === ']') { i++; break; }
            }
            return arr;
        }
        function parseObject(): any {
            let obj: any = {};
            i++;
            if (str[i] === '}') { i++; return obj; }
            while (true) {
                let key = parseString();
                i++;
                obj[key] = parseValue();
                if (str[i] === ',') i++;
                else if (str[i] === '}') { i++; break; }
            }
            return obj;
        }
        return parseValue();
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, as each character is processed once.
  • 🧺 Space complexity: O(n), for the recursion stack and the resulting object/array.