Last Updated: 5 Mar, 2021
Sort Array Of Strings
Easy
Asked in companies
You are given an array of strings 'ARRSTR[]' of size 'N' and a character 'C'. Your task is to sort the 'ARRSTR[]' according to the new alphabetical order that starts with the given character 'C'.
Note:
1) The character ‘C’ is a lowercase English alphabet that is given as input.
2) For example, if the character is 'C' is "d" then, the alphabetical order starts with "d" will look like {d,e,f,....,y,z,a,b,c}.
3) Every string in the array consists of only lowercase English alphabets.
Input Format:
The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow.
The first line of each test case contains a positive integer 'N' denoting the size of the array and a character 'C', as described in the problem statement.
The second line of each test case contains a sequence of 'N' space-separated strings denoting the elements of the array.
Output Format:
For each test case, print in a new line a sequence of 'N' space-separated strings after sorting according to the new alphabetical order given in the problem.
Output for each test case will be printed in a separate 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 <= 1000
'C' is a lowercase English alphabet.
1 <= | ARRSTR[i] | <= 9, where 1 <= i <= N.
Time Limit: 1sec
Approaches
Approach: The idea here is to use a data structure HashMap to store each character’s order in the new alphabetical order, starting with a letter c (given in the problem). Now, start comparing the strings in the ‘ARRSTR[]’ using HashMap that has been created to define the order.
Suppose that we are comparing two strings of ‘ARRSTR[]’ named ‘X’ and ‘Y’. Let us assume that we have found the first different character at the ith index, so if the order (already stored in the HashMap) of ‘X[i]’ is less than the ‘Y[i]’, then ‘X’ is to placed in the front of ‘Y’ (not necessarily adjacent to ‘Y’), and vice-versa.
Algorithm is as follows:
- Create a string consisting of the new alphabetical order named as ‘NEWORDER’. So, ‘NEWORDER’ must contain all the characters starting from character ‘C’ to ‘z’, and then ‘a’ to the character just before 'C'. For example, if the character ‘C’ is ‘d’, then, ‘NEWORDER’ = “defghijklmnopqrstuvwxyzabc”.
- Create a HashMap named as ‘HMAP’ to store the order.
- Run a loop to iterate through the ‘NEWORDER’ with the help of variable ‘i’:
- Make ‘HMAP[NEWORDER[i]]’ = ‘i’.
- Now define a custom comparator function named ‘COMPARE’ to sort the strings according to the new alphabetical order.
- Sort the strings with the help of ‘COMPARE’.
- Return the array of strings ‘ARRSTR’.
bool compare(string x, string y) :
- This function is used to sort the strings in the order already defined in the HashMap.
- Run a loop with the variable ‘i’ = 0 to min('X.length()' , ‘Y.length()’) :
- If the ith character of both the strings is the same, then just continue.
- Else, return ‘HMAP[X[i]]’ < ‘HMAP[Y[i]]’.
- If the loop completes then, return ‘X.length()’ < ‘Y.length()’ (because all the characters are the same, so the smaller string should be placed before the larger one in terms of length).