Last Updated: 17 Apr, 2021
English To Maths
Easy
Ninja is trying to decipher a string 'S' that contains an out-of-order English representation of the digits 0 - 9.
Your task is to help Ninja to get back the digits in ascending order.
For example :
Given string ‘S’ = “toowen”, on the rearrangement of this string we get “onetwo” which implies “12”.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.The 'T' test cases follow.
The first and the only line of each test case contains a single string 'S'.
Output Format :
For each test case, print a string of digits 0-9 in ascending order which we can get after rearrangement of the given string 'S'.
The output for each test case is printed in a separate line.
Constraints :
1 <= T <= 5
1 <= N <= 5000
‘S’ is always valid.
Where ‘N’ is the length of the string ‘S’.
Time limit: 1 sec
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
Here, we are going to use an observation that some alphabets are unique to some digits as illustrated below:
- Zero: only digit with ‘Z’
- Two: only digit with ‘W’
- Four: only digit with ‘U’
- Six: only digit with ‘X’
- Eight: only digit with ‘G’
And as the string is always valid, to find the occurrence of other digits we need to find the frequency of any single character from the digit's English word.
To find “H” in three we just need to subtract the total “H” frequency with the frequency of “8” because both contain “H”.
Similarly, to find five we find the remaining “F” after four, to find seven we need to find “V” and for one and nine we need to calculate “O” and “I” respectively.
Algorithm:
- Declare a map ‘FREQ’.
- Traverse the string ‘S’ using ‘i’ ranges from 0 to S.length.
- FREQ[S[i]]++
- Declare an array ‘CNT’ of size 10 initialised with 0.
- CNT[0] = FREQ[‘z’]
- CNT[2] = FREQ[‘w’]
- CNT[4] = FREQ[‘u’]
- CNT[6] = FREQ[‘x’]
- CNT[8] = FREQ[‘g’]
- CNT[3] = FREQ[‘h’] - CNT[8]
- CNT[5] = FREQ[‘f’] - CNT[4]
- CNT[7] = FREQ[‘v’] - CNT[5]
- CNT[1] = FREQ[‘o’] - CNT[0] - CNT[2] - CNT[4]
- CNT[9] = FREQ[‘i’] - CNT[6] - CNT[5] - CNT[8]
- Declare a string ‘RES’ = “”
- For i in range (0, 10):
- Repeat the steps till CNT[i] > 0.
- CNT[i]--
- RES += tostring(i)
- Return ‘RES’.
In this approach, we are just implementing approach 1 differently. Instead of calculating each digit frequency one by one, we will use a loop to count the frequency of each digit.
Algorithm:
- Declare a map ‘FREQ’.
- Traverse the string ‘S’ using ‘i’ ranges from 0 to S.length.
- FREQ[S[i]]++
- Declare three array ‘ORDER’, ‘DIGITS’ and ‘CNT’.
- Initialise ‘ORDER’ := {0, 2, 4, 6, 8, 1, 3, 5, 7, 9}.
- Initialise ‘WORDS’ := {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}.
- Traverse the array ‘ORDER’ using ‘i’ from 0 to ORDER.size
- Declare two variables ‘NUM’:= ORDER[i] and ‘MINI’ := int.max .
- Traverse the string WORDS[NUM] using ‘j’ from 0 to WORDS[i].size.
- MINI := min(FREQ[ WORDS[NUM][j] ],MINI).
- Traverse the string WORDS[NUM] using ‘j’ from 0 to WORDS[i].size.
- FREQ[ WORDS[NUM][j] ] -= MINI.
- CNT[NUM] = MINI.
- Declare an empty string ‘RES’ := “”.
- Traverse the array ‘CNT’ using ‘i’ from 0 to 10.
- Repeat steps till CNT[i] > 0.
- RES += (‘0’ + i )
- CNT[i]--
- Repeat steps till CNT[i] > 0.
- Return ‘RES’.