- Arrays, Hash, Sorting, Strings

Sort an array of strings based on the given order | Set-2

Given an array of strings words[] and the sequential order of alphabets, the task is to sort the array according to the given order. Assume that the dictionary and the words only contain lowercase English alphabets.Examples: Input: words[] = {“hello”, “geeksforgeeks”}, order[] = “hlabcdefgijkmnopqrstuvwxyz”Output: hello geeksforgeeks Explanation: According to the given order ‘h’ occurs before ‘g’ and hence the words are considered to be sorted.Input: words = {“word”, “world”, “row”}, order = “worldabcefghijkmnpqstuvxyz” Output: world word row Explanation: According to the given order ‘l’ occurs before ‘d’ hence the words “world” will be kept first.  Approach: The given problem is already discussed in the article here. This article suggests a different approach that uses hashing. Since an order of alphabets is given, it can be used as a key where order[i]th alphabet can be replaced by the ith alphabet. For instance, in the given order[] = “hlabcdefgijkmnopqrstuvwxyz”, character ‘h’ can be replaced by ‘a’, character ‘l’ can be replaced by ‘b’, and so on. Using that observation the given problem can be solved by following the below steps:Create a hashFunction that accepts a key as an argument and replaces all the characters of the string according to the given key i.e, character x will be replaced by character stored in key[x].Use an unordered map encode, which store the sequence of characters as per the given order i.e, encode[‘h’] = ‘a’, encode[‘l’] = ‘b’… and so on. Similarly, store the reverse in decode i.e, decode[‘a’] = ‘h’, decode[‘b’] = ‘l’… and so on which can be used to restore the original array.Sort the array after hashing it using encode as the key.Restore the strings in the sorted array using decode as the key.Below is the implementation of the above approach:C++#include using namespace std;  void hashFunction(vector& words,                  unordered_map key){    for (auto& x : words) {        for (int i = 0; i < x.size(); i++) {            x[i] = key[x[i]];        }    }}  void printSorted(vector words, string order){            unordered_map encode, decode;          for (int i = 0; i < 26; i++) {                        encode[order[i]] = 'a' + i;                          decode['a' + i] = order[i];    }              hashFunction(words, encode);          sort(words.begin(), words.end());                  hashFunction(words, decode);          for (auto x : words) {        cout