LeetCode Solutions Blog

Convert JSON String to Object

Number: 2851

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given a JSON string that represents an object, array, number, string, boolean, or null, return the parsed JSON value as the corresponding data structure (object, array, primitive, etc.). The input string is guaranteed to be valid JSON but you are not allowed to use the built-in JSON.parse (or similar) method.

Key Insights

Use a recursive descent parsing approach to handle the various JSON types.
Create helper functions to parse objects, arrays, strings, numbers, booleans, and null.
Maintain an index/pointer to navigate through the string.
Skip whitespace between tokens.
Since escape characters are not present, string parsing can be simplified by looking for the next double quote.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string (each character is processed a constant number of times).
Space Complexity: O(n) in the worst-case scenario (for example when the JSON structure is deeply nested or when storing the entire parsed data).

Solution

We implement a recursive descent parser that uses an index to track our position in the string. Based on the character at the current pointer, we decide which parsing routine to call:

If the character is '{', we call the object-parsing function.
If it is '[', we call the array-parsing function.
If it is '"', we parse a string.
For numbers, booleans (true/false), and null, we convert them appropriately.

Each function consumes characters until it reaches the end of that specific JSON structure. Whitespace is skipped during parsing to ensure separators and tokens are correctly identified. Special attention is given to the structure of objects (key-value pairs) and arrays (comma separated elements).

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments.

class JSONParser:
    def __init__(self, s):
        self.s = s              # JSON string to parse
        self.i = 0              # Current index in the string

    def skip_whitespace(self):
        # Skip any whitespace characters
        while self.i < len(self.s) and self.s[self.i] in ' \n\r\t':
            self.i += 1

    def parse(self):
        # Entry point for parsing; calls parse_value and returns the result
        self.skip_whitespace()
        result = self.parse_value()
        self.skip_whitespace()
        return result

    def parse_value(self):
        self.skip_whitespace()
        if self.i >= len(self.s):
            return None
        char = self.s[self.i]
        if char == '{':
            return self.parse_object()
        elif char == '[':
            return self.parse_array()
        elif char == '"':
            return self.parse_string()
        elif char in '-0123456789':
            return self.parse_number()
        elif self.s.startswith("true", self.i):
            self.i += 4
            return True
        elif self.s.startswith("false", self.i):
            self.i += 5
            return False
        elif self.s.startswith("null", self.i):
            self.i += 4
            return None
        else:
            raise ValueError("Unexpected character: " + char)

    def parse_object(self):
        # Parse a JSON object starting with '{'
        result = {}
        self.i += 1  # Skip '{'
        self.skip_whitespace()
        if self.s[self.i] == '}':
            self.i += 1  # Empty object; skip '}'
            return result
        while True:
            self.skip_whitespace()
            key = self.parse_string()  # Keys must be strings
            self.skip_whitespace()
            if self.s[self.i] != ':':
                raise ValueError("Expected ':' after key in object")
            self.i += 1  # Skip ':'
            self.skip_whitespace()
            value = self.parse_value()  # Parse the value associated with the key
            result[key] = value
            self.skip_whitespace()
            if self.s[self.i] == '}':  # End of object
                self.i += 1
                break
            elif self.s[self.i] == ',':
                self.i += 1  # Skip ',' to move to the next key-value pair
            else:
                raise ValueError("Expected ',' or '}' in object")
        return result

    def parse_array(self):
        # Parse a JSON array starting with '['
        result = []
        self.i += 1  # Skip '['
        self.skip_whitespace()
        if self.s[self.i] == ']':
            self.i += 1  # Empty array; skip ']'
            return result
        while True:
            self.skip_whitespace()
            value = self.parse_value()  # Parse the next value in the array
            result.append(value)
            self.skip_whitespace()
            if self.s[self.i] == ']':
                self.i += 1  # End of array
                break
            elif self.s[self.i] == ',':
                self.i += 1  # Skip ',' to move to the next element
            else:
                raise ValueError("Expected ',' or ']' in array")
        return result

    def parse_string(self):
        # Parse a JSON string (assume no escape sequences)
        self.i += 1  # Skip the opening double quote
        start = self.i
        # Find the next double quote
        while self.i < len(self.s) and self.s[self.i] != '"':
            self.i += 1
        value = self.s[start:self.i]
        self.i += 1  # Skip the closing double quote
        return value

    def parse_number(self):
        # Parse a JSON number, which may have a sign and decimals
        start = self.i
        if self.s[self.i] == '-':
            self.i += 1
        while self.i < len(self.s) and self.s[self.i].isdigit():
            self.i += 1
        # Check for a decimal point
        if self.i < len(self.s) and self.s[self.i] == '.':
            self.i += 1
            while self.i < len(self.s) and self.s[self.i].isdigit():
                self.i += 1
        num_str = self.s[start:self.i]
        # Convert to int if possible, otherwise to float
        if '.' in num_str:
            return float(num_str)
        else:
            return int(num_str)

# Example usage:
def parse_json_string(s):
    parser = JSONParser(s)
    return parser.parse()

# You can test the function:
# print(parse_json_string('{"a":2,"b":[1,2,3]}'))