Convert JSON String to Object

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:

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:

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

Example 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

JavaScript

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();
    }
}

TypeScript

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.