Ordenar una array de strings según el orden dado | Conjunto-2

Dada una array de palabras de strings [] y el orden secuencial de los alfabetos, la tarea es ordenar la array de acuerdo con el orden dado. Suponga que el diccionario y las palabras solo contienen alfabetos ingleses en minúsculas.

Ejemplos: 

Entrada: palabras[] = {“hola”, “geeksforgeeks”}, orden[] = “hlabcdefgijkmnopqrstuvwxyz”
Salida: hola geeksforgeeks 
Explicación:  De acuerdo con el orden dado, ‘h’ aparece antes de ‘g’ y, por lo tanto, las palabras se consideran ordenado

Entrada: palabras = {“palabra”, “mundo”, “fila”}, orden = “mundoabcefghijkmnpqstuvxyz” 
Salida: palabra mundial fila 
Explicación:  De acuerdo con el orden dado, ‘l’ aparece antes de ‘d’, por lo tanto, las palabras “mundo” mantenerse primero.  

Enfoque: El problema dado ya se discute en el artículo aquí . Este artículo sugiere un enfoque diferente que utiliza hashing . Dado que se da un orden de alfabetos, se puede usar como una clave donde el orden [i] ^th alfabeto puede ser reemplazado por el i ^th alfabeto. Por ejemplo, en el orden dado[] = “hlabcdefgijkmnopqrstuvwxyz”, el carácter ‘h’ se puede reemplazar por ‘a’ , el carácter ‘l’ se puede reemplazar por ‘b’ , y así sucesivamente . Usando esa observación, el problema dado se puede resolver siguiendo los pasos a continuación:

• Cree una función hash que acepte una clave como argumento y reemplace todos los caracteres de la string de acuerdo con la clave dada, es decir, el carácter x será reemplazado por el carácter almacenado en key[x] .
• Use una codificación de mapa desordenada , que almacena la secuencia de caracteres según el orden dado, es decir, encode[‘h’] = ‘a’ , encode[‘l’] = ‘b’… y así sucesivamente. Del mismo modo, almacene el reverso en decode , es decir, decode[‘a’] = ‘h’ , decode[‘b’] = ‘l’ … y así sucesivamente, que se pueden usar para restaurar la array original.
• Ordene la array después de codificarla usando codificar como clave.
• Restaure las strings en la array ordenada usando decode como clave.

A continuación se muestra la implementación del enfoque anterior:

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to replace all the
// characters in the array of strings
// according to the given key
void hashFunction(vector<string>& words,
                  unordered_map<char, char> key)
{
    for (auto& x : words) {
        for (int i = 0; i < x.size(); i++) {
            x[i] = key[x[i]];
        }
    }
}
 
// Function to print the strings
// according to the given order
void printSorted(vector<string> words, string order)
{
    // Stores the characters in order
    // to encode and decode the string
    unordered_map<char, char> encode, decode;
 
    // Loop to iterate over all characters
    for (int i = 0; i < 26; i++) {
        // Replace the order[i]th character
        // from the ith character
        encode[order[i]] = 'a' + i;
 
        // Replace the ith character
        // from the order[i]th character
        decode['a' + i] = order[i];
    }
 
    // Function Call to replace all characters
    // in words according to encode
    hashFunction(words, encode);
 
    // STL Function to sort the array
    sort(words.begin(), words.end());
 
    // Function Call to replace all characters
    // in words according to decode in order
    // to restore original strings
    hashFunction(words, decode);
 
    // Printing the sorted order of words
    for (auto x : words) {
        cout << x << " ";
    }
}
 
// Driver code
int main()
{
    vector<string> words = { "word", "world", "row" };
    string order = "worldabcefghijkmnpqstuvxyz";
 
    // Function Call
    printSorted(words, order);
 
    return 0;
}

# Python 3 program of the above approach
 
# Function to replace all the
# characters in the array of strings
# according to the given key
def hashFunction(words, key):
    for x in words:
        x = list(x)
        for i in range(len(x)):
            x[i] = key[x[i]]
        x = ''.join(x)
 
# Function to print the strings
# according to the given order
def printSorted(words, order):
   
    # Stores the characters in order
    # to encode and decode the string
    encode = {}
    decode = {}
 
    # Loop to iterate over all characters
    for i in range(26):
        # Replace the order[i]th character
        # from the ith character
        encode[order[i]] = chr(ord('a') + i)
 
        # Replace the ith character
        # from the order[i]th character
        decode[chr(ord('a') + i)] = order[i]
 
    # Function Call to replace all characters
    # in words according to encode
    hashFunction(words, encode)
 
    # STL Function to sort the array
    words.sort(reverse = True)
 
    # Function Call to replace all characters
    # in words according to decode in order
    # to restore original strings
    hashFunction(words, decode)
 
    # Printing the sorted order of words
    for x in words:
        print(x,end = " ")
 
# Driver code
if __name__ == '__main__':
    words = ["word", "world", "row"]
    order = "worldabcefghijkmnpqstuvxyz"
 
    # Function Call
    printSorted(words, order)
     
    # This code is contributed by ipg2016107.

<script>
// Javascript program of the above approach
 
// Function to replace all the
// characters in the array of strings
// according to the given key
function hashFunction(words, key) {
  for (x of words) {
    for (let i = 0; i < x.length; i++) {
      x[i] = key.get(x[i]);
    }
  }
  console.log(words);
}
 
// Function to print the strings
// according to the given order
function printSorted(words, order) {
  // Stores the characters in order
  // to encode and decode the string
  let encode = new Map();
  let decode = new Map();
 
  // Loop to iterate over all characters
  for (let i = 0; i < 26; i++) {
    // Replace the order[i]th character
    // from the ith character
    encode.set(order[i], "a".charCodeAt(0) + i);
 
    // Replace the ith character
    // from the order[i]th character
    decode.set("a".charCodeAt(0) + i, order[i]);
  }
 
  // Function Call to replace all characters
  // in words according to encode
  hashFunction(words, encode);
 
  // Function to sort the array
  words.sort().reverse();
 
  // Function Call to replace all characters
  // in words according to decode in order
  // to restore original strings
  hashFunction(words, decode);
 
  // Printing the sorted order of words
  for (x of words) {
    document.write(x + " ");
  }
}
 
// Driver code
 
let words = ["word", "world", "row"];
let order = "worldabcefghijkmnpqstuvxyz";
 
// Function Call
printSorted(words, order);
 
</script>

world word row 

Complejidad de tiempo: O(N*M*log(N)) donde M es la longitud promedio de todas las strings.
Espacio Auxiliar: O(1)