Last Updated: 21 Mar, 2021
Goodness of a String
Moderate
Asked in companies
You are provided with a string ‘S’ which indicates the nested list. For example: “[1, [2, 3], [4, [5, 6] ] ]”. Each number present in the list has some depth. The depth of a particular number is the number of nested lists in which it is present. Consider the previous example in which the number ‘1’ is at depth 1, numbers ‘2’, ‘3’, and ‘4’ are at depth 2, and numbers ‘5’ and ‘6’ are at depth 3.
You have to find the goodness of the given string/nested list. The goodness of a string is the sum of the product of depths and elements present in the string.
For Example:
S = “[1, [2, 3], [4, [5, 6] ] ]”
Total depth = 1*1 + 2*2 + 3*2 + 4*2 + 5*3 + 6*3 = 52
Note:
1. The given string may be empty.
2. The string will not contain any white spaces.
3. You have to take the modulo with 10 ^ 9 + 7 as the answer may be very large.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain a string ‘S’ which denotes the given nested list.
Output Format:
For each test case, print a single line containing a single integer denoting the goodness of the given string.
The output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= |S| <= 100000
1 <= ES[ i ] <= 10^5
Where “|S|” is the length of the given string, “ES[ i ]” is the element/number stored in the string at the “i-th” position.
Time limit: 1 sec
Approaches
The basic idea is to traverse through the complete string, make a variable to hold the current depth and whenever found a number just add it into our answer after multiplying it with the current depth.
The steps are as follows:
- Create two variables “depth” and “ans” to store the current depth and the answer. Initialize both of them with 0.
- Iterate through ‘s’. (say, iterator = ‘i’)
- Check if s[ i ] is ‘ , ’ then continue iterations.
- Else if, s[ i ] is ‘ [ ‘ which means new depth has started and so, increment “depth” by 1.
- Else if, s[ i ] is ‘ ] ‘ which means one depth has ended and so, decrement “depth” by 1.
- Else, there must be a number at s[ i ] and so we have to take all the digits of this number.
- Create a variable “num” that will be going to store the current number.
- Iterate through ‘s’ again. (say, iterator = ‘j’)
- If, s[ j ] becomes equal to ‘ , ‘ or ‘ ] ‘ which means the number has been already picked and so stop the further iterations.
- Else, push this digit into “num”.
- Multiply “num” with “depth” under modulo with 10^9 + 7 and then add the result into the “ans”.
- Set ‘i’ to ‘j’ - 1 as the ‘j’ characters representing the number that has been already picked.
- Return “ans”.