Dada una array de strings arr[] de tamaño N , la tarea es ordenar la array de strings en orden lexicográfico y si mientras se ordenan dos strings A y B , si la string A es el prefijo de la string B , entonces la string B debería aparecer en el orden ordenado.
Ejemplos:
Entrada: arr[] = {“sol”, “luna”, “simulacro”}
Salida:
simulacro
luna
sol
Explicación:
La clasificación lexicográfica es simulacro, luna y sol.Entrada: arr[] = {“geeks”, “geeksfor”, “geeksforgeeks”}
Salida:
geeksforgeeks
geeksfor
geeks
Enfoque: la idea es ordenar la array dada de strings usando la función de ordenación incorporada usando la función de comparación a continuación. La función de comparación utilizada para verificar si alguna string aparece como una substring en otra string usando la función de comparación() en C++ , luego debería organizarlos en orden decreciente de su longitud.
C++
bool my_compare(string a, string b) { // If any string is a substring then // return the size with greater length if (a.compare(0, b.size(), b) == 0 || b.compare(0, a.size(), a) == 0) return a.size() & gt; b.size(); // Else return lexicographically // smallest string else return a & lt; b; }
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the vector void Print(vector<string> v) { for (auto i : v) cout << i << endl; } // Comparator function to sort the // array of string wrt given conditions bool my_compare(string a, string b) { // Check if a string is present as // prefix in another string, then // compare the size of the string // and return the larger size if (a.compare(0, b.size(), b) == 0 || b.compare(0, a.size(), a) == 0) return a.size() > b.size(); // Else return lexicographically // smallest string else return a < b; } // Driver Code int main() { // GIven vector of strings vector<string> v = { "batman", "bat", "apple" }; // Calling Sort STL with my_compare // function passed as third parameter sort(v.begin(), v.end(), my_compare); // Function call to print the vector Print(v); return 0; }
apple batman bat
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rishabhtyagi2306 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA