Programa C++ para verificar si la string dada puede estar formada por otras dos strings o sus permutaciones

Dada una string str y una array de strings arr[] , la tarea es verificar si la string dada puede estar formada por cualquiera de los pares de strings de la array o sus permutaciones. Ejemplos:

Entrada: str = “amazon”, arr[] = {“loa”, “azo”, “ft”, “amn”, “lka”} Salida: Sí Las strings elegidas son “amn” y “azo” que pueden ser reorganizado como «amazon». Entrada: str = «geeksforgeeks», arr[] = {«geeks», «geek», «for»} Salida: No

Método 1: en este enfoque, comenzamos clasificando la string dada, luego ejecutamos dos bucles anidados para seleccionar dos strings de la array dada a la vez y concatenarlas. Luego ordenamos la string resultante que obtuvimos después de la concatenación.
Luego comparamos esta string con la string dada y verificamos si son iguales o no. Si se encuentra igual devolvemos verdadero.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if str can be
// generated from any permutation of the
// two strings selected from the given vector
bool isPossible(vector<string> v, string str)
{
 
    // Sort the given string
    sort(str.begin(), str.end());
 
    // Select two strings at a time from given vector
    for (int i = 0; i < v.size() - 1; i++) {
        for (int j = i + 1; j < v.size(); j++) {
 
            // Get the concatenated string
            string temp = v[i] + v[j];
 
            // Sort the resultant string
            sort(temp.begin(), temp.end());
 
            // If the resultant string is equal
            // to the given string str
            if (temp.compare(str) == 0) {
                return true;
            }
        }
    }
 
    // No valid pair found
    return false;
}
 
// Driver code
int main()
{
    string str = "amazon";
    vector<string> v{ "fds", "oxq", "zoa", "epw", "amn" };
 
    if (isPossible(v, str))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Yes

Complejidad de tiempo: O(nlogn+m ² klogk) donde n es el tamaño de la string dada, m es el tamaño de la array dada y k es el tamaño máximo obtenido al sumar dos strings cualesquiera (que es básicamente la suma de las tamaño de las dos strings más largas en la array dada).

Método 2: la ordenación por conteo se puede utilizar para reducir el tiempo de ejecución del enfoque anterior. La ordenación por conteo usa una tabla para almacenar el conteo de cada carácter. Tenemos 26 alfabetos, por lo tanto, creamos una array de tamaño 26 para almacenar recuentos de cada carácter en la string. Luego tome los caracteres en orden creciente para obtener la string ordenada. A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 26
 
// Function to sort the given string
// using counting sort
void countingsort(string& s)
{
    // Array to store the count of each character
    int count[MAX] = { 0 };
    for (int i = 0; i < s.length(); i++) {
        count[s[i] - 'a']++;
    }
    int index = 0;
 
    // Insert characters in the string
    // in increasing order
    for (int i = 0; i < MAX; i++) {
        int j = 0;
        while (j < count[i]) {
            s[index++] = i + 'a';
            j++;
        }
    }
}
 
// Function that returns true if str can be
// generated from any permutation of the
// two strings selected from the given vector
bool isPossible(vector<string> v, string str)
{
 
    // Sort the given string
    countingsort(str);
 
    // Select two strings at a time from given vector
    for (int i = 0; i < v.size() - 1; i++) {
        for (int j = i + 1; j < v.size(); j++) {
 
            // Get the concatenated string
            string temp = v[i] + v[j];
 
            // Sort the resultant string
            countingsort(temp);
 
            // If the resultant string is equal
            // to the given string str
            if (temp.compare(str) == 0) {
                return true;
            }
        }
    }
 
    // No valid pair found
    return false;
}
 
// Driver code
int main()
{
    string str = "amazon";
    vector<string> v{ "fds", "oxq", "zoa", "epw", "amn" };
 
    if (isPossible(v, str))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Yes

Complejidad temporal: O(n+m ² k) donde n es el tamaño de la string dada, m es el tamaño de la array dada y k es el tamaño máximo obtenido al sumar dos strings cualesquiera (que es básicamente la suma de las tamaño de las dos strings más largas en la array dada).

¡ Consulte el artículo completo sobre Comprobar si la string dada puede estar formada por otras dos strings o sus permutaciones para obtener más detalles!