2759. Convert JSON String to Object
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, andparseNullrecognize and handle the respective literalstrue,false, andnull.parseNumberrecognizes sequences of digits, possibly including a minus sign and decimal point, which constitute a number.parseStringhandles quoted sequences of characters, which represent strings in JSON.parseArraychecks for a list of values enclosed in square brackets[]and parses each value in the list.parseObjectlooks 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).parseValueis 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.
In a binary min heap, the maximum element can be found in:
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
iis used to keep track of the current position within the stringstr. The length of the input string is stored inn. -
Parsing Boolean and Null Values: The functions
parseTrue,parseFalse, andparseNullcheck for the literal valuestrue,false, andnull, respectively, and update the indexito move past the parsed value. -
Parsing Numbers: The function
parseNumberaccumulates in a stringsthe consecutive characters that make up a number until it encounters a delimiter (a comma,, a closing brace}, or a closing bracket]). It then convertssto a number usingNumber(s). -
Parsing Strings:
parseStringprocesses 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
parseArrayfunction 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 callsparseValueto parse that element and adds the result to the array. -
Parsing Objects: Similarly,
parseObjectcreates 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:
parseValueis 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 literaltrueorfalseif it starts withtorf,nullif it starts withn, 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
parseValueenable 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
ipast the parsed value to the next relevant character in the input string, or to the end of the string.parseValueis 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).
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Example 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:
1"{"name":"John","age":30,"isStudent":false}"
-
Initialize the variables: The index
istarts at 0, and we'll store the length of the string in variablen. -
The first character is
{, indicating that we need to parse an object. We callparseObjectto handle this. -
In
parseObject, we skip past the opening{and look for the first key. The next set of characters""name":""are processed byparseString, which will return the key name "name". We then skip the colon and callparseValueto determine the type of value. -
parseValuesees the opening quote", indicating a string value. It then callsparseStringto 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
parseStringhandling the""age":""which returns "age" as the key. -
The next character is
3, indicating a number value.parseNumberis called and processes30, 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 encounterfalse.parseFalseis called and returnsfalseas the value for the key "isStudent". -
Finally, we find the closing
}, so we conclude the object parsing. -
At this point,
ihas 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:
1{ 2 "name": "John", 3 "age": 30, 4 "isStudent": false 5}
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()
1231import 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}
1451#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]}");
1361function 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}
137What's the relationship between a tree and a graph?
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).
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.