2759. Convert JSON String to Object

Hard

Problem Description

The given LeetCode problem asks us to write a function that takes a string str as input and returns parsedStr, which is the result of parsing str as JSON. The input string is guaranteed to be a valid JSON string, meaning it will only contain values that are valid JSON types such as strings, numbers, arrays, objects, booleans, or null. It is also specified that the string lacks invisible and escape characters, and string values within the JSON contain only alphanumeric characters. An essential constraint is that we must implement this parsing functionality without using the built-in JSON.parse function.

Intuition

To solve this problem, we need to understand the structure of a JSON string. JSON (JavaScript Object Notation) is a lightweight data interchange format that is easy for humans to read and write and easy for machines to parse and generate. A JSON object consists of key-value pairs enclosed in curly braces {}, an array is an ordered list of values enclosed in square brackets [], and values can be a string, number, object, array, boolean (true/false), or null.

Our solution approach is, therefore, to define a parser that can recognize and handle each of these cases. We do this through recursive descent parsing, which is a common technique used to parse expressions and structured text. The parser contains functions to handle each type of value that can be encountered:

parseTrue, parseFalse, and parseNull recognize and handle the respective literals true, false, and null.
parseNumber recognizes sequences of digits, possibly including a minus sign and decimal point, which constitute a number.
parseString handles quoted sequences of characters, which represent strings in JSON.
parseArray checks for a list of values enclosed in square brackets [] and parses each value in the list.
parseObject looks for key-value pairs enclosed in curly brackets {} and parses each key (which will be a string) and each value (which could be any JSON data type).
parseValue is a helper function that determines which of the above functions to call based on the current character of the input string.

We maintain an index i which points to the current character in the string being parsed. As we parse elements of the string, we advance i to move through the string. When a parse function is called, it processes its part of the string and returns the appropriate JavaScript value (object, array, string, number, boolean, or null). The main parsing function, parseValue, delegates to the other functions based on the initial character(s) of the current element being parsed, allowing us to recursively construct the data structure that represents the JSON input.

The parser's functions collectively read through the input string, interpret the structure using the rules of JSON syntax, and construct an in-memory representation (like what JSON.parse does). The assumption that the input string is valid JSON and does not contain invisible characters or escape characters (aside from those in strings) simplifies the parser's implementation since it does not need to handle error cases or deal with such complexities. The result is an efficient parser that uses a straightforward approach to convert a JSON string representation into the corresponding JavaScript data structure.

Solution Approach

The solution for parsing a JSON string without using the built-in JSON.parse method involves a technique called recursive descent parsing. This technique consists of a collection of functions that "descend" through the grammar of the input—in this case, the JSON structure—processing each piece as it appears. Below is the explanation of the various parts of the solution:

Variables: An index i is used to keep track of the current position within the string str. The length of the input string is stored in n.
Parsing Boolean and Null Values: The functions parseTrue, parseFalse, and parseNull check for the literal values true, false, and null, respectively, and update the index i to move past the parsed value.
Parsing Numbers: The function parseNumber accumulates in a string s the consecutive characters that make up a number until it encounters a delimiter (a comma ,, a closing brace }, or a closing bracket ]). It then converts s to a number using Number(s).
Parsing Strings: parseString processes characters within double quotes ". It handles potentially escaped characters by checking for backslashes \ and advancing the index accordingly. Once it finds the closing double quote, it returns the accumulated string and advances the index past the quote.
Parsing Arrays: The parseArray function creates an array, advances past the opening bracket [, and continues until it encounters the closing bracket ]. For every element it finds (separated by commas), it calls parseValue to parse that element and adds the result to the array.
Parsing Objects: Similarly, parseObject creates an object, advances past the opening brace {, and loops until it reaches the closing brace }. It looks for string keys, followed by a colon :, and then parses the value associated with that key. Each key-value pair is added to the object.
Making Decisions: parseValue is the central function that determines the type of the next value in the JSON string by looking at the current character: an object if it's {, an array if it's [, a string if it's ", a boolean literal true or false if it starts with t or f, null if it starts with n, and a number for anything else (typically a digit or a minus).
Recursion and Looping: Both arrays and objects may contain nested structures (arrays within arrays, objects within objects, etc.). The recursive calls to parseValue enable the function to handle arbitrary depths of nesting. Loops allow parsing through multiple keys in an object or multiple values in an array.
Ending the Parsing: Each helper parsing function advances the index i past the parsed value to the next relevant character in the input string, or to the end of the string. parseValue is called initially to start the parsing process. Once all the characters are processed, the top-level parsed structure is returned.

Algorithmically, the solution uses simple control structures (if-else, while loops) to navigate and recognize patterns in the input string. Recursion is a key component that simplifies the handling of nested structures. This implementation can be characterized by its linear time complexity because it processes each character in the input exactly once (or slightly more in the case of backtracking during recursive calls).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take an example of a JSON string to illustrate the solution approach. We will use the following simple JSON string for our walkthrough:

"{"name":"John","age":30,"isStudent":false}"

Initialize the variables: The index i starts at 0, and we'll store the length of the string in variable n.
The first character is {, indicating that we need to parse an object. We call parseObject to handle this.
In parseObject, we skip past the opening { and look for the first key. The next set of characters ""name":"" are processed by parseString, which will return the key name "name". We then skip the colon and call parseValue to determine the type of value.
parseValue sees the opening quote ", indicating a string value. It then calls parseString to process the characters "John". The result "John" is stored as the value for the key "name".
We then move past the comma to the next key-value pair, with parseString handling the ""age":"" which returns "age" as the key.
The next character is 3, indicating a number value. parseNumber is called and processes 30, then returns it as the value for the key "age".
We continue past the comma to the next key "isStudent", and after the colon, we encounter false. parseFalse is called and returns false as the value for the key "isStudent".
Finally, we find the closing }, so we conclude the object parsing.
At this point, i has reached the end of the input string, and the entire JSON string has been successfully parsed into a JavaScript object.

The functions work together to interpret input string sections and construct a data structure that mirrors what you would get from JSON.parse. Each component of the JSON structure is handled by a specialized function that delegates to other functions as needed, ensuring that the entire structure is parsed correctly, regardless of nesting level or complexity. The final output we obtain is the following JavaScript object:

{
  "name": "John",
  "age": 30,
  "isStudent": false
}

This step-by-step process showcases recursion and orderly parsing of each JSON element using the helper functions without ever needing to invoke JSON.parse.

Solution Implementation

1def json_parse(json_str):
2    length = len(json_str)
3    index = 0
4
5    def parse_true():
6        # Parses a literal `true` value
7        nonlocal index
8        index += 4
9        return True
10
11    def parse_false():
12        # Parses a literal `false` value
13        nonlocal index
14        index += 5
15        return False
16
17    def parse_null():
18        # Parses a literal `null` value
19        nonlocal index
20        index += 4
21        return None
22
23    def parse_number():
24        # Parses a number value
25        nonlocal index
26        num_str = ''
27        while index < length:
28            char = json_str[index]
29            if char in [',', '}', ']']:
30                break
31            num_str += char
32            index += 1
33        return float(num_str)
34
35    def parse_array():
36        # Parses an array value
37        nonlocal index
38        array = []
39        index += 1  # Skip past the opening bracket '['
40
41        while index < length:
42            char = json_str[index]
43            if char == ']':
44                index += 1  # Skip past the closing bracket ']'
45                break
46            if char == ',':
47                index += 1  # Skip past the comma
48                continue
49
50            value = parse_value()
51            array.append(value)
52
53        return array
54
55    def parse_string():
56        # Parses a string value
57        nonlocal index
58        string_val = ''
59        index += 1  # Skip past the opening quote '"'
60
61        while index < length:
62            char = json_str[index]
63
64            if char == '"':
65                index += 1  # Skip past the closing quote '"'
66                break
67
68            if char == '\\':
69                index += 1  # Skip past the escape character '\'
70                string_val += json_str[index]
71            else:
72                string_val += char
73
74            index += 1
75
76        return string_val
77
78    def parse_object():
79        # Parses an object value
80        nonlocal index
81        obj = {}
82        index += 1  # Skip past the opening curly brace '{'
83
84        while index < length:
85            char = json_str[index]
86            if char == '}':
87                index += 1  # Skip past the closing curly brace '}'
88                break
89
90            if char == ',':
91                index += 1  # Skip past the comma
92                continue
93
94            key = parse_string()
95            index += 1  # Skip past the colon
96            value = parse_value()
97            obj[key] = value
98
99        return obj
100
101    def parse_value():
102        # Determines the appropriate parse function based on the current character
103        nonlocal index
104        char = json_str[index]
105
106        if char == '{':
107            return parse_object()
108        elif char == '[':
109            return parse_array()
110        elif char == '"':
111            return parse_string()
112        elif char == 't':
113            return parse_true()
114        elif char == 'f':
115            return parse_false()
116        elif char == 'n':
117            return parse_null()
118        else:
119            return parse_number()
120
121    # Initiates the parsing process
122    return parse_value()
123

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6public class JsonParser {
7
8    // Entry method to parse a JSON string
9    public static Object jsonParse(String str) {
10        final int length = str.length();
11        int[] index = new int[] { 0 }; 
12
13        return parseValue(str, length, index);
14    }
15
16    // Parses a boolean `true` value
17    private static boolean parseTrue(String str, int length, int[] index) {
18        index[0] += 4;
19        return true;
20    }
21
22    // Parses a boolean `false` value
23    private static boolean parseFalse(String str, int length, int[] index) {
24        index[0] += 5;
25        return false;
26    }
27
28    // Parses a null value
29    private static Object parseNull(String str, int length, int[] index) {
30        index[0] += 4;
31        return null;
32    }
33
34    // Parses a number value
35    private static Number parseNumber(String str, int length, int[] index) {
36        StringBuilder numStr = new StringBuilder();
37        while (index[0] < length) {
38            char ch = str.charAt(index[0]);
39            if (ch == ',' || ch == '}' || ch == ']') {
40                break;
41            }
42            numStr.append(ch);
43            index[0]++;
44        }
45        return Double.parseDouble(numStr.toString()); // Number is assumed to be a double
46    }
47
48    // Parses an array value
49    private static List<Object> parseArray(String str, int length, int[] index) {
50        List<Object> array = new ArrayList<>();
51        index[0]++; // Skip past the opening bracket '['
52
53        while (index[0] < length) {
54            char ch = str.charAt(index[0]);
55            if (ch == ']') {
56                index[0]++; // Skip past the closing bracket ']'
57                break;
58            }
59
60            if (ch == ',') {
61                index[0]++; // Skip past the comma
62                continue;
63            }
64
65            Object value = parseValue(str, length, index);
66            array.add(value);
67        }
68
69        return array;
70    }
71
72    // Parses a string value
73    private static String parseString(String str, int length, int[] index) {
74        StringBuilder stringVal = new StringBuilder();
75        index[0]++; // Skip past the opening quote '"'
76
77        while (index[0] < length) {
78            char ch = str.charAt(index[0]);
79
80            if (ch == '"') {
81                index[0]++; // Skip past the closing quote '"'
82                break;
83            }
84
85            if (ch == '\\') {
86                index[0]++; // Skip past the escape character '\'
87                stringVal.append(str.charAt(index[0]));
88            } else {
89                stringVal.append(ch);
90            }
91
92            index[0]++;
93        }
94
95        return stringVal.toString();
96    }
97
98    // Parses an object value
99    private static Map<String, Object> parseObject(String str, int length, int[] index) {
100        Map<String, Object> object = new HashMap<>();
101        index[0]++; // Skip past the opening curly brace '{'
102
103        while (index[0] < length) {
104            char ch = str.charAt(index[0]);
105            if (ch == '}') {
106                index[0]++; // Skip past the closing curly brace '}'
107                break;
108            }
109
110            if (ch == ',') {
111                index[0]++; // Skip past the comma
112                continue;
113            }
114
115            String key = parseString(str, length, index);
116            index[0]++; // Skip past the colon
117            Object value = parseValue(str, length, index);
118            object.put(key, value);
119        }
120
121        return object;
122    }
123
124    // Determines the appropriate parse function based on the current character
125    private static Object parseValue(String str, int length, int[] index) {
126        char ch = str.charAt(index[0]);
127        switch (ch) {
128            case '{':
129                return parseObject(str, length, index);
130            case '[':
131                return parseArray(str, length, index);
132            case '"':
133                return parseString(str, length, index);
134            case 't':
135                return parseTrue(str, length, index);
136            case 'f':
137                return parseFalse(str, length, index);
138            case 'n':
139                return parseNull(str, length, index);
140            default:
141                return parseNumber(str, length, index);
142        }
143    }
144}
145

1#include <string>
2#include <cctype>
3
4// JSON parser in C++
5class JSONParser {
6private:
7    std::string str;  // the JSON string to be parsed
8    size_t length;    // the length of the JSON string
9    size_t index;     // the current index in the JSON string
10
11    // Parses a literal `true` value
12    bool parseTrue() {
13        index += 4;
14        return true;
15    }
16
17    // Parses a literal `false` value
18    bool parseFalse() {
19        index += 5;
20        return false;
21    }
22
23    // Parses a literal `null` value
24    std::nullptr_t parseNull() {
25        index += 4;
26        return nullptr;
27    }
28
29    // Parses a number value
30    double parseNumber() {
31        std::string numStr;
32        while (index < length) {
33            char currentChar = str[index];
34            // Stop parsing if a comma, closing brace, or closing bracket is found
35            if (currentChar == ',' || currentChar == '}' || currentChar == ']') {
36                break;
37            }
38            numStr += currentChar;
39            index++;
40        }
41        return std::stod(numStr); // Convert string to double
42    }
43
44    // Parses an array value
45    std::vector<any> parseArray() {
46        std::vector<any> array;
47        index++; // skip past the opening bracket '['
48
49        while (index < length && str[index] != ']') {
50            if (str[index] == ',') {
51                index++; // skip past the comma
52            } else {
53                array.push_back(parseValue());
54            }
55        }
56      
57        index++; // skip past the closing bracket ']'
58        return array;
59    }
60
61    // Parses a string value
62    std::string parseString() {
63        std::string stringVal;
64        index++; // skip past the opening quote '"'
65
66        while (index < length) {
67            char currentChar = str[index];
68
69            if (currentChar == '"') {
70                index++; // skip past the closing quote '"'
71                break;
72            }
73
74            // handle escaped characters
75            if (currentChar == '\\') {
76                index++; // skip past the escape character '\'
77                stringVal += str[index];
78            } else {
79                stringVal += currentChar;
80            }
81
82            index++;
83        }
84
85        return stringVal;
86    }
87
88    // Parses an object value
89    std::map<std::string, any> parseObject() {
90        std::map<std::string, any> object;
91        index++; // skip past the opening curly brace '{'
92
93        while (index < length && str[index] != '}') {
94            if (str[index] == ',') {
95                index++; // skip past the comma
96            } else {
97                std::string key = parseString();
98                index++; // skip past the colon
99                any value = parseValue();
100                object[key] = value;
101            }
102        }
103
104        index++; // skip past the closing curly brace '}'
105        return object;
106    }
107
108    // Determines the appropriate parse function based on the current character
109    any parseValue() {
110        char currentChar = str[index];
111        switch(currentChar) {
112            case '{': return parseObject();
113            case '[': return parseArray();
114            case '"': return parseString();
115            case 't': return parseTrue();
116            case 'f': return parseFalse();
117            case 'n': return parseNull();
118            default: return parseNumber();
119        }
120    }
121
122public:
123    any jsonParse(const std::string& jsonString) {
124        this->str = jsonString;
125        this->length = jsonString.length();
126        this->index = 0;
127      
128        // Initiates the parsing process
129        return parseValue();
130    }
131};
132
133// Usage example:
134// JSONParser parser;
135// any result = parser.jsonParse("{\"key\": [true, false, null, 123]}");
136

1function jsonParse(str: string): any {
2  const length = str.length;
3  let index = 0;
4
5  // Parses a literal `true` value
6  function parseTrue(): boolean {
7    index += 4;
8    return true;
9  }
10
11  // Parses a literal `false` value
12  function parseFalse(): boolean {
13    index += 5;
14    return false;
15  }
16
17  // Parses a literal `null` value
18  function parseNull(): null {
19    index += 4;
20    return null;
21  }
22
23  // Parses a number value
24  function parseNumber(): number {
25    let numStr = '';
26    while (index < length) {
27      const char = str[index];
28      if (char === ',' || char === '}' || char === ']') {
29        break;
30      }
31      numStr += char;
32      index++;
33    }
34    return Number(numStr);
35  }
36
37  // Parses an array value
38  function parseArray(): any[] {
39    const array: any[] = [];
40    index++; // Skip past the opening bracket '['
41
42    while (index < length) {
43      const char = str[index];
44      if (char === ']') {
45        index++; // Skip past the closing bracket ']'
46        break;
47      }
48
49      if (char === ',') {
50        index++; // Skip past the comma
51        continue;
52      }
53
54      const value = parseValue();
55      array.push(value);
56    }
57
58    return array;
59  }
60
61  // Parses a string value
62  function parseString(): string {
63    let stringVal = '';
64    index++; // Skip past the opening quote '"'
65
66    while (index < length) {
67      const char = str[index];
68
69      if (char === '"') {
70        index++; // Skip past the closing quote '"'
71        break;
72      }
73
74      if (char === '\\') {
75        index++; // Skip past the escape character '\'
76        stringVal += str[index];
77      } else {
78        stringVal += char;
79      }
80
81      index++;
82    }
83
84    return stringVal;
85  }
86
87  // Parses an object value
88  function parseObject(): any {
89    const object: any = {};
90    index++; // Skip past the opening curly brace '{'
91
92    while (index < length) {
93      const char = str[index];
94      if (char === '}') {
95        index++; // Skip past the closing curly brace '}'
96        break;
97      }
98
99      if (char === ',') {
100        index++; // Skip past the comma
101        continue;
102      }
103
104      const key = parseString();
105      index++; // Skip past the colon
106      const value = parseValue();
107      object[key] = value;
108    }
109
110    return object;
111  }
112
113  // Determines the appropriate parse function based on the current character
114  function parseValue(): any {
115    const char = str[index];
116    switch(char) {
117      case '{':
118        return parseObject();
119      case '[':
120        return parseArray();
121      case '"':
122        return parseString();
123      case 't':
124        return parseTrue();
125      case 'f':
126        return parseFalse();
127      case 'n':
128        return parseNull();
129      default:
130        return parseNumber();
131    }
132  }
133
134  // Initiates the parsing process
135  return parseValue();
136}
137

Time and Space Complexity

The time complexity of the given JSON parsing function is primarily driven by how many times we iterate over the input string (str). The function traverses the entire string once, going through each character and processing it, which would result in a time complexity of O(n) where n is the length of the string. The reason it does not exceed O(n) is that the function does not re-visit characters (except in the case of escaped characters within strings), and all operations within the parseValue branches (e.g., parseObject, parseArray, parseString, parseNumber, parseTrue, parseFalse, parseNull) are linear in terms of the number of characters they process. None of these operations involves nested loops dependent on the size of the input string.

Space complexity is a measure of the amount of memory that the function uses in relation to the input size. This function creates data structures (objects and arrays) recursively that correspond to nested structures in the JSON string. Undefined depth of nesting in the JSON string could lead to a stack depth equal to the nesting depth, but each call uses constant space except for the created arrays and objects. Thus, the space complexity would be O(n) for the output data structure size plus O(d) for the recursive call stack where d is the depth of the JSON object (considering the worst-case scenario where each character could contribute to the depth). However, if we consider the size of the output data structure to be separate from the complexity calculation, the remaining space usage (call stack, primitive variables, and counters) would be O(d) due to the recursive nature of parseValue. This depends on the JSON string's structure rather than its length.

Therefore, the time complexity is O(n) and the space complexity, including the output data, is O(n + d). Excluding the output data, the space complexity is O(d).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: