Compruebe si dos strings son equivalentes o no según la condición dada

Posted on by Rudeus Greyrat

Dadas dos strings A y B de igual tamaño. Dos strings son equivalentes cualquiera de las siguientes condiciones es cierta: 
1) Ambos son iguales. O, 
2) Si dividimos la string A en dos substrings contiguas del mismo tamaño A 1 y A 2 y la string B en dos substrings contiguas del mismo tamaño B 1 y B 2 , entonces uno de los siguientes debería ser correcto: 
 

  • A 1 es recursivamente equivalente a B 1 y A 2 es recursivamente equivalente a B 2
  • A 1 es recursivamente equivalente a B 2 y A 2 es recursivamente equivalente a B 1

Compruebe si las strings dadas son equivalentes o no. Escriba SÍ o NO.
Ejemplos: 
 

Entrada: A = “aaba”, B = “abaa” 
Salida: SÍ 
Explicación: Dado que la condición 1 no se cumple, podemos dividir la string A en “aaba” = “aa” + “ba” y la string B en “abaa ” = “ab” + “aa”. Aquí, la segunda subcondición se cumple donde A 1 es igual a B 2 y A 2 es recursivamente igual a B 1
Entrada: A = “aabb”, B = “abab” 
Salida: NO 
 

Solución ingenua: una solución simple es considerar todos los escenarios posibles. Verifique primero si ambas strings son iguales, devuelva «SÍ», de lo contrario, divida las strings y verifique si A 1 = B 1 y A 2 = B 2 o A 1 = B 2 y A 2 = B 1 usando cuatro llamadas recursivas. La complejidad de esta solución sería O(n 2 ), donde n es el tamaño de la string.
Solución eficiente:Definamos la siguiente operación en la string S. Podemos dividirla en dos mitades y, si queremos, podemos intercambiarlas. Y también, podemos aplicar recursivamente esta operación a sus dos mitades. Mediante una observación cuidadosa, podemos ver que si después de aplicar la operación en alguna string A, podemos obtener B, luego de aplicar la operación en B podemos obtener A. Y para las dos strings dadas, podemos encontrar recursivamente la string menos lexicográficamente que se puede obtener de ellos. Las strings obtenidas si son iguales, la respuesta es SI, en caso contrario NO. Por ejemplo, la string menos lexicográficamente para «aaba» es «aaab». Y menos lexicográficamente, la string para «abaa» también es «aaab». Por lo tanto, ambos son equivalentes.
A continuación se muestra la implementación del enfoque anterior. 
 

C++

// CPP Program to find whether two strings
// are equivalent or not according to given
// condition
#include <bits/stdc++.h>
using namespace std;
 
// This function returns the least lexicogr
// aphical string obtained from its two halves
string leastLexiString(string s)
{
    // Base Case - If string size is 1
    if (s.size() & 1)
        return s;
 
    // Divide the string into its two halves
    string x = leastLexiString(s.substr(0,
                                        s.size() / 2));
    string y = leastLexiString(s.substr(s.size() / 2));
 
    // Form least lexicographical string
    return min(x + y, y + x);
}
 
bool areEquivalent(string a, string b)
{
  return (leastLexiString(a) == leastLexiString(b));
}
 
// Driver Code
int main()
{
    string a = "aaba";
    string b = "abaa";
    if (areEquivalent(a, b))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
 
    a = "aabb";
    b = "abab";
    if (areEquivalent(a, b))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Java

// Java Program to find whether two strings
// are equivalent or not according to given
// condition
class GfG
{
 
// This function returns the least lexicogr
// aphical String obtained from its two halves
static String leastLexiString(String s)
{
    // Base Case - If String size is 1
    if (s.length() == 1)
        return s;
 
    // Divide the String into its two halves
    String x = leastLexiString(s.substring(0,
                                        s.length() / 2));
    String y = leastLexiString(s.substring(s.length() / 2));
 
    // Form least lexicographical String
    return String.valueOf((x + y).compareTo(y + x));
}
 
static boolean areEquivalent(String a, String b)
{
    return !(leastLexiString(a).equals(leastLexiString(b)));
}
 
// Driver Code
public static void main(String[] args)
{
    String a = "aaba";
    String b = "abaa";
    if (areEquivalent(a, b))
        System.out.println("Yes");
    else
        System.out.println("No");
 
    a = "aabb";
    b = "abab";
    if (areEquivalent(a, b))
        System.out.println("Yes");
    else
        System.out.println("No");
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python 3 Program to find whether two strings
# are equivalent or not according to given
# condition
 
# This function returns the least lexicogr
# aphical string obtained from its two halves
def leastLexiString(s):
     
    # Base Case - If string size is 1
    if (len(s) & 1 != 0):
        return s
 
    # Divide the string into its two halves
    x = leastLexiString(s[0:int(len(s) / 2)])
    y = leastLexiString(s[int(len(s) / 2):len(s)])
 
    # Form least lexicographical string
    return min(x + y, y + x)
 
def areEquivalent(a,b):
    return (leastLexiString(a) == leastLexiString(b))
 
# Driver Code
if __name__ == '__main__':
    a = "aaba"
    b = "abaa"
    if (areEquivalent(a, b)):
        print("YES")
    else:
        print("NO")
 
    a = "aabb"
    b = "abab"
    if (areEquivalent(a, b)):
        print("YES")
    else:
        print("NO")
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# Program to find whether two strings
// are equivalent or not according to given
// condition
using System;
class GFG
{
 
// This function returns the least lexicogr-
// aphical String obtained from its two halves
static String leastLexiString(String s)
{
    // Base Case - If String size is 1
    if (s.Length == 1)
        return s;
 
    // Divide the String into its two halves
    String x = leastLexiString(s.Substring(0,
                               s.Length / 2));
    String y = leastLexiString(s.Substring(
                               s.Length / 2));
 
    // Form least lexicographical String
    return ((x + y).CompareTo(y + x).ToString());
}
 
static Boolean areEquivalent(String a, String b)
{
    return !(leastLexiString(a).Equals(
             leastLexiString(b)));
}
 
// Driver Code
public static void Main(String[] args)
{
    String a = "aaba";
    String b = "abaa";
    if (areEquivalent(a, b))
        Console.WriteLine("YES");
    else
        Console.WriteLine("NO");
 
    a = "aabb";
    b = "abab";
    if (areEquivalent(a, b))
        Console.WriteLine("YES");
    else
        Console.WriteLine("NO");
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
    // Javascript Program to find whether two strings
    // are equivalent or not according to given
    // condition
     
    // This function returns the least lexicogr-
    // aphical String obtained from its two halves
    function leastLexiString(s)
    {
        // Base Case - If String size is 1
        if (s.length == 1)
            return s;
 
        // Divide the String into its two halves
        let x = leastLexiString(s.substring(0,
                                   s.length / 2));
        let y = leastLexiString(s.substring(
                                   s.length / 2));
 
        // Form least lexicographical String
        if((x + y) < (y + x))
        {
            return (x+y);
        }
        else{
            return (y+x);
        }
    }
 
    function areEquivalent(a, b)
    {
        return (leastLexiString(a) == leastLexiString(b));
    }
     
    let a = "aaba";
    let b = "abaa";
    if (areEquivalent(a, b))
        document.write("YES" + "</br>");
    else
        document.write("NO" + "</br>");
  
    a = "aabb";
    b = "abab";
    if (areEquivalent(a, b))
        document.write("YES" + "</br>");
    else
        document.write("NO" + "</br>");
 
// This code is contributed by decode2207.
</script>

PHP

<?php
// PHP Program to find whether two strings
// are equivalent or not according to given
// condition
 
// This function returns the least lexicogr
// aphical string obtained from its two halves
function leastLexiString($s)
{
    // Base Case - If string size is 1
    if (strlen($s) & 1)
        return $s;
 
    // Divide the string into its two halves
    $x = leastLexiString(substr($s, 0,floor(strlen($s) / 2)));
    $y = leastLexiString(substr($s,floor(strlen($s) / 2),strlen($s)));
 
    // Form least lexicographical string
    return min($x.$y, $y.$x);
}
 
function areEquivalent($a, $b)
{
    return (leastLexiString($a) == leastLexiString($b));
}
 
    // Driver Code
    $a = "aaba";
    $b = "abaa";
    if (areEquivalent($a, $b))
        echo "YES", "\n";
    else
        echo "NO", "\n";
 
    $a = "aabb";
    $b = "abab";
    if (areEquivalent($a, $b))
        echo "YES", "\n";
    else
        echo "NO","\n";
 
// This code is contributed by Ryuga
?>
Producción: 

YES
NO

 

Complejidad de tiempo: O(N*logN), donde N es el tamaño de la string.
Espacio Auxiliar: O(logN)
 

Publicación traducida automáticamente

Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *