Programa Java 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

// Java implementation of the approach
import java.util.*;
  
class GFG 
{
  
// Function that returns true if str can be
// generated from any permutation of the
// two strings selected from the given vector
static boolean isPossible(Vector<String> v, String str)
{
  
    // Sort the given string
    str = sortString(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.get(i) + v.get(j);
  
            // Sort the resultant string
            temp = sortString(temp);
  
            // If the resultant string is equal
            // to the given string str
            if (temp.compareTo(str) == 0) 
            {
                return true;
            }
        }
    }
  
    // No valid pair found
    return false;
}
  
// Method to sort a string alphabetically 
public static String sortString(String inputString) 
{ 
    // convert input string to char array 
    char tempArray[] = inputString.toCharArray(); 
      
    // sort tempArray 
    Arrays.sort(tempArray); 
      
    // return new sorted string 
    return new String(tempArray); 
} 
  
// Driver code
public static void main(String[] args) 
{
    String str = "amazon";
    String []arr = { "fds", "oxq", "zoa", "epw", "amn" };
    Vector<String> v = new Vector<String>(Arrays.asList(arr));
  
    if (isPossible(v, str))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
  
// This code is contributed by Rajput-Ji

Método 2:

clasificación de 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:

// Java implementation of the approach 
import java.util.*;
  
class GFG 
{
static int MAX = 26; 
  
// Function to sort the given string 
// using counting sort 
static String countingsort(char[] s) 
{ 
      
    // Array to store the count of each character 
    int []count = new int[MAX]; 
    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++] = (char)(i + 'a'); 
            j++; 
        } 
    } 
        return String.valueOf(s);
} 
  
// Function that returns true if str can be 
// generated from any permutation of the 
// two strings selected from the given vector 
static boolean isPossible(Vector<String> v, 
                                 String str) 
{ 
  
    // Sort the given string 
    str=countingsort(str.toCharArray()); 
  
    // 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.get(i) + v.get(j); 
  
            // Sort the resultant string 
            temp = countingsort(temp.toCharArray()); 
  
            // If the resultant string is equal 
            // to the given string str 
            if (temp.equals(str)) 
            { 
                return true; 
            } 
        } 
    } 
  
    // No valid pair found 
    return false; 
} 
  
// Driver code 
public static void main(String[] args) 
{
    String str = "amazon"; 
    String []arr = { "fds", "oxq", "zoa", "epw", "amn" };
    Vector<String> v = new Vector<String>(Arrays.asList(arr));
  
    if (isPossible(v, str)) 
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
  
// This code is contributed by 29AjayKumar

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