PRETTY JSON

Easy
0/40
Average time to solve is 10m
profile
Contributed by
32 upvotes
Asked in companies
FacebookDeltaXD.E.Shaw

Problem statement

You are given a string 'STR' representing JSON object. Return an array of strings denoting JSON objects with proper indentation.

Rules for proper indentation: 
1. Every inner brace should increase one indentation to the following lines.
2. Every close brace should decrease one indentation to the same line and the following lines.
3. Every ‘,’ will mean a separate line.
4. The indents can be increased with an additional 4 spaces or ‘/t’.
Example: 
Let the input be: "{A:"B",C:{D:"E",F:{G:"H",I:"J"}}}"

Then we return the following array of strings: 
{ 
    A:"B",
    C: 
    { 
        D:"E",
        F: 
        { 
            G:"H",
            I:"J"
        } 
    } 
}

Note that for every new brace we are putting an additional 4 spaces or \t.
Note: 
1. [] and {} are only acceptable braces in this case.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.

The first line of each test case contains the string ‘STR’.
Output Format: 
For each test case, return an array of strings containing the indented JSON file.

Output for each test case will be printed in a new line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 2*10^3

Where 'N' denotes the length of the string.

Time limit: 1 sec
Sample Input 1:
2
["foo", {"bar":["baz",null,1.0,2]}]
[{"EmployeeID":1,"Name":"Abhishek","Designation":"SoftwareEngineer"}]
Sample Output 1:
[
    "foo",

    {
        "bar":
        [
            "baz",
            null,
            1.0,
            2
        ]
    }
]
[
    {
        "Employee ID":1,
        "Name":"Abhishek",
        "Designation":"SoftwareEngineer"
    }
]
Explanation of sample input 1 :
Test Case 1:

In the first test case,
We can see that we have 3 braces so we print when we encounter ‘[‘ we indent by leaving 4 spaces and then put “foo” in the string. 
Then we indent 4 more spaces and put “bar”.
Finally, we indent 4 more spaces for the last opening brace and then print baz.
Since we have ‘,’ after ‘bazz’ we make a new line for null and the numbers. 
Finally, we close the brackets taking care of the proper indentation.


In the second test case,

We have 2 braces only. After the first ‘[‘ we leave 4 spaces and put ‘{‘ in the string.
Then we put the string data taking care to change the line after every ‘,’  and de-indent for every closing brace.
Sample Input 2:
1
{"EmployeeID":2,"Name":"Garima","Designation":"EmailMarketing Specialist"}
Sample Output 2:
{
    "Employee ID":2,
    "Name":"Garima",
    "Designation":"EmailMarketing Specialist"
}
Hint

Just find the braces and put appropriate spaces.

Approaches (1)
Iterative Approach

The key idea in solving this problem is to simply iterate through the given string and construct our array of strings. We need to take care of the following points:

 

  1. Whenever we encounter some kind of opening brace, we add 4 spaces to all the below lines in the beginning
  2. Whenever we encounter some kind of closing brace, we delete 4 spaces to all the below lines from the beginning
  3. When we encounter a ‘,’ we change the line.
  4. In the case of a colon, we do not change the line unless we have a brace right next to it.

 

Below is the detailed algorithm:

 

  • We make an array of strings ‘RESULT’ to store the result.
  • We maintain a variable ‘brace’ which contains the number of braces encountered till now.
  • Initially, it is 1.
  • Now we iterate through the string and check for the following cases:

    

  1. If the current character is an opening brace and is the first opening brace, we just make a new row in the result array and increment the brace by 1.If it is not a first opening brace, we make a new row and add ‘BRACE’ number of ‘\t’ or 4 spaces in the string and add a new line.
  2. If the current character is a closing brace, we first decrease ‘BRACE’ by 1 and then add a brace number of ‘\t’ characters.
  3. If we have a ‘,’ we simply add a new line. But we need to take care of the corner case that if a ‘,’ is followed by a brace, we need not do anything as the new line operation will be taken care of by the brace.
  4. If we have a ‘:’ we simply print it unless we have a colon followed by an opening brace in which we make a new line and do the same as we did in point1.
  5. Finally, we return the ‘RESULT’.

 

Do check your code for the following corner cases:

  1. } followed by ,
  2. } or ] followed by } or ]
  3. { or [ followed by { or [
Time Complexity

O(N ^ 2), where ‘N’ is the length of the string.

 

The time required for the construction of the array of strings will be in order of N ^ 2. Hence, the overall time complexity is O(N ^ 2).

Space Complexity

O(N ^ 2), where ‘N’ is the length of the string.

 

In the worst case, we can have all braces, and that makes the space complexity will be O(N ^ 2).

Code Solution
(100% EXP penalty)
PRETTY JSON
Full screen
Console