Programa Python3 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: 

# Python3 implementation of the approach
 
# Function that returns true if str can be
# generated from any permutation of the
# two strings selected from the given vector
def isPossible(v, string ) :
     
    char_list = list(string)
     
    # Sort the given string
    char_list.sort()
     
    # Select two strings at a time from given vector
    for i in range(len(v)-1) :
        for j in range(len(v)) :
             
            # Get the concatenated string
            temp = v[i] + v[j];
             
            # Sort the resultant string
            temp_list = list(temp)
            temp_list.sort()
             
            # If the resultant string is equal
            # to the given string str
            if (temp_list == char_list) :
                return True;
                 
    # No valid pair found
    return False;
 
# Driver code
if __name__ == "__main__" :
 
    string = "amazon";
    v = [ "fds", "oxq", "zoa", "epw", "amn" ];
 
    if (isPossible(v, string)):
        print("Yes");
    else :
        print("No");
         
# This code is contributed by AnkitRai01

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: 

# Python 3 implementation of the approach
MAX = 26
 
# Function to sort the given string
# using counting sort
def countingsort(s):
    # Array to store the count of each character
    count = [0 for i in range(MAX)]
    for i in range(len(s)):
        count[ord(s[i]) - ord('a')] += 1
    index = 0
 
    # Insert characters in the string
    # in increasing order
     
    for i in range(MAX):
        j = 0
        while (j < count[i]):
            s = s.replace(s[index],chr(97+i))
            index += 1
            j += 1
         
 
# Function that returns true if str can be
# generated from any permutation of the
# two strings selected from the given vector
def isPossible(v, str1):
    # Sort the given string
    countingsort(str1);
 
    # Select two strings at a time from given vector
    for i in range(len(v)-1):
        for j in range(i + 1,len(v),1):
            # Get the concatenated 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 == str1):
                return False
             
    # No valid pair found
    return True
 
# Driver code
if __name__ == '__main__':
    str1 = "amazon"
    v = ["fds", "oxq", "zoa", "epw", "amn"]
 
    if (isPossible(v, str1)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by
# Surendra_Gangwar

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!