Encuentre el índice i tal que el prefijo de S1 y el sufijo de S2 hasta que forme un palíndromo cuando se concatena

Dadas dos strings A y B de igual longitud, la tarea es encontrar un índice i tal que A[0…i] y B[i+1…n-1] den un palíndromo cuando se concatenan entre sí. Si no es posible encontrar dicho índice, imprima -1 .
Ejemplos: 
 

Entrada: S1 = “abcdf”, S2 = “sfgba” 
Salida:
S1[0..1] = “ab”, S2[2..n-1] = “gba” 
S1 + S2 = “abgba” que es un palíndromo.
Entrada: S1 = “abcda”, S2 = “bacbs” 
Salida: -1 
 

Enfoque sencillo: 
 

  • Iterar de 0 a n (longitud de la string) y copiar i -ésimo carácter de S1 a otra string , digamos S.
  • Ahora tome otra string temporal Temp y copie los caracteres de S2 del índice i +1 a n .
  • Ahora comprueba si la string (S + Temp) es palíndromo o no.

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if s is palindrome
bool isPalindrome(string s)
{
    int i = 0;
    int j = s.length() - 1;
 
    while (i < j) {
        if (s[i] != s[j])
            return false;
        i++;
        j--;
    }
 
    return true;
}
 
// Function to return the required index
int getIndex(string S1, string S2, int n)
{
 
    string S = "";
 
    for (int i = 0; i < n; i++) {
 
        // Copy the ith character in S
        S = S + S1[i];
        string Temp = "";
 
        // Copy all the character of string s2 in Temp
        for (int j = i + 1; j < n; j++)
            Temp += S2[j];
 
        // Check whether the string is palindrome
        if (isPalindrome(S + Temp)) {
            return i;
        }
    }
 
    return -1;
}
 
// Driver code
int main()
{
    string S1 = "abcdf", S2 = "sfgba";
    int n = S1.length();
 
    cout << getIndex(S1, S2, n);
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
// Function that returns true if s is palindrome
static boolean isPalindrome(String s)
{
    int i = 0;
    int j = s.length() - 1;
 
    while (i < j)
    {
        if (s.charAt(i) != s.charAt(j))
            return false;
        i++;
        j--;
    }
 
    return true;
}
 
// Function to return the required index
static int getIndex(String S1, String S2, int n)
{
 
    String S = "";
 
    for (int i = 0; i < n; i++)
    {
 
        // Copy the ith character in S
        S = S + S1.charAt(i);
        String Temp = "";
 
        // Copy all the character of string
        // s2 in Temp
        for (int j = i + 1; j < n; j++)
            Temp += S2.charAt(j);
 
        // Check whether the string is palindrome
        if (isPalindrome(S + Temp))
        {
            return i;
        }
    }
 
    return -1;
}
 
// Driver code
public static void main(String[] args)
{
    String S1 = "abcdf", S2 = "sfgba";
    int n = S1.length();
 
    System.out.println(getIndex(S1, S2, n));
}
}
 
// This code is contributed by Code_Mech.

Python3

# Python3 implementation of the approach
 
# Function that returns true if s is palindrome
def isPalindrome(s):
    i = 0;
    j = len(s) - 1;
 
    while (i < j):
        if (s[i] is not s[j]):
            return False;
        i += 1;
        j -= 1;
 
    return True;
 
# Function to return the required index
def getIndex(S1, S2, n):
 
    S = "";
 
    for i in range(n):
 
        # Copy the ith character in S
        S = S + S1[i];
        Temp = "";
 
        # Copy all the character of string s2 in Temp
        for j in range(i + 1, n):
            Temp += S2[j];
 
        # Check whether the string is palindrome
        if (isPalindrome(S + Temp)):
            return i;
 
    return -1;
 
# Driver code
S1 = "abcdf"; S2 = "sfgba";
n = len(S1);
 
print(getIndex(S1, S2, n));
 
# This code is contributed by Rajput-Ji

C#

// C# implementation of the approach
using System;
class GFG
{
     
// Function that returns true if
// s is palindrome
static bool isPalindrome(string s)
{
    int i = 0;
    int j = s.Length - 1;
 
    while (i < j)
    {
        if (s[i] != s[j])
            return false;
        i++;
        j--;
    }
 
    return true;
}
 
// Function to return the required index
static int getIndex(string S1,
                    string S2, int n)
{
    string S = "";
 
    for (int i = 0; i < n; i++)
    {
 
        // Copy the ith character in S
        S = S + S1[i];
        string Temp = "";
 
        // Copy all the character of string
        // s2 in Temp
        for (int j = i + 1; j < n; j++)
            Temp += S2[j];
 
        // Check whether the string
        // is palindrome
        if (isPalindrome(S + Temp))
        {
            return i;
        }
    }
 
    return -1;
}
 
// Driver code
public static void Main()
{
    string S1 = "abcdf", S2 = "sfgba";
    int n = S1.Length;
 
    Console.WriteLine(getIndex(S1, S2, n));
}
}
 
// This code is contributed by Code_Mech.

PHP

<?php
// PHP implementation of the approach
 
// Function that returns true if s
// is palindrome
function isPalindrome($s)
{
    $i = 0;
    $j = strlen($s) - 1;
 
    while ($i < $j)
    {
        if ($s[$i] != $s[$j])
            return false;
        $i++;
        $j--;
    }
 
    return true;
}
 
// Function to return the required index
function getIndex($S1, $S2, $n)
{
    $S = "";
 
    for ($i = 0; $i < $n; $i++)
    {
 
        // Copy the ith character in S
        $S = $S . $S1[$i];
        $Temp = "";
 
        // Copy all the character of string
        // s2 in Temp
        for ($j = $i + 1; $j < $n; $j++)
            $Temp .= $S2[$j];
 
        // Check whether the string is palindrome
        if (isPalindrome($S . $Temp))
        {
            return $i;
        }
    }
 
    return -1;
}
 
// Driver code
$S1 = "abcdf"; $S2 = "sfgba";
$n = strlen($S1);
 
echo getIndex($S1, $S2, $n);
 
// This code is contributed
// by Akanksha Rai
?>

Javascript

<script>
 
    // JavaScript implementation of the approach
     
    // Function that returns true if
    // s is palindrome
    function isPalindrome(s)
    {
        let i = 0;
        let j = s.length - 1;
 
        while (i < j)
        {
            if (s[i] != s[j])
                return false;
            i++;
            j--;
        }
 
        return true;
    }
 
    // Function to return the required index
    function getIndex(S1, S2, n)
    {
        let S = "";
 
        for (let i = 0; i < n; i++)
        {
 
            // Copy the ith character in S
            S = S + S1[i];
            let Temp = "";
 
            // Copy all the character of string
            // s2 in Temp
            for (let j = i + 1; j < n; j++)
                Temp += S2[j];
 
            // Check whether the string
            // is palindrome
            if (isPalindrome(S + Temp))
            {
                return i;
            }
        }
 
        return -1;
    }
     
    let S1 = "abcdf", S2 = "sfgba";
    let n = S1.length;
   
    document.write(getIndex(S1, S2, n));
     
</script>
Producción: 

1

 

Complejidad de tiempo: O(n 2 )
Enfoque eficiente : el enfoque eficiente será observar que la string concatenada será un palíndromo si el primer carácter de la primera string coincide con el último carácter de la segunda string, ya que estamos considerando el prefijo de la primera string y el sufijo de segunda cuerda.
 

  • Comience a iterar la primera string desde el principio usando un puntero, digamos i , y la segunda string desde el final usando un puntero, digamos j hasta i < j y s1[i] == s2[j] .
  • Compruebe si los dos punteros i y j son iguales en el primer desajuste.
  • En caso afirmativo, devuelva el índice i, es decir, podemos concatenar las strings s1[0..i] y s2[j..N] para formar un palíndromo.
  • De lo contrario, compruebe si s1[i..j] o s2[i..j] es un palíndromo. Si es así, aún podemos concatenar s1[0..j] + s2[j+1, N-1] o s1[0..i-1] + s2[i..N-1] para formar un palíndromo.
  • De lo contrario, devuelve -1.

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

C++

// C++ program to implement the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if the sub-string
// starting from index i and ending at index j
// is a palindrome
bool isPalindrome(string s, int i, int j)
{
    while (i < j) {
        if (s[i] != s[j])
            return false;
        i++;
        j--;
    }
    return true;
}
 
// Function to get the required index
int getIndex(string s1, string s2, int len)
{
    int i = 0, j = len - 1;
 
    // Start comparing the two strings
    // from both ends.
    while (i < j) {
        // Break from the loop at first mismatch
        if (s1[i] != s2[j]) {
            break;
        }
 
        i++;
        j--;
    }
 
    // If it is possible to concatenate
    // the strings to form palindrome,
    // return index
    if (i == j) {
        return i - 1;
    }
 
    // If remaining part for s2
    // is palindrome
    else if (isPalindrome(s2, i, j))
        return i - 1;
 
    // If remaining part for s1
    // is palindrome
    else if (isPalindrome(s1, i, j))
        return j;
 
    // If not possible, return -1
    return -1;
}
 
// Driver Code
int main()
{
    string s1 = "abcdf", s2 = "sfgba";
    int len = s1.length();
 
    cout << getIndex(s1, s2, len);
 
    return 0;
}

Java

// Java implementation of the above approach
class GFG
{
 
// Function that returns true if the sub-String
// starting from index i and ending at index j
// is a palindrome
static boolean isPalindrome(String s, int i, int j)
{
    while (i < j)
    {
        if (s.charAt(i) != s.charAt(j))
            return false;
        i++;
        j--;
    }
    return true;
}
 
// Function to get the required index
static int getIndex(String s1, String s2, int len)
{
    int i = 0, j = len - 1;
 
    // Start comparing the two Strings
    // from both ends.
    while (i < j)
    {
        // Break from the loop at first mismatch
        if (s1.charAt(i) != s2.charAt(j))
        {
            break;
        }
 
        i++;
        j--;
    }
 
    // If it is possible to concatenate
    // the Strings to form palindrome,
    // return index
    if (i == j)
    {
        return i - 1;
    }
 
    // If remaining part for s2
    // is palindrome
    else if (isPalindrome(s2, i, j))
        return i - 1;
 
    // If remaining part for s1
    // is palindrome
    else if (isPalindrome(s1, i, j))
        return j;
 
    // If not possible, return -1
    return -1;
}
 
// Driver Code
public static void main(String args[])
{
    String s1 = "abcdf", s2 = "sfgba";
    int len = s1.length();
 
    System.out.println( getIndex(s1, s2, len));
 
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to implement the
# above approach
 
# Function that returns true if the sub-string
# starting from index i and ending at index j
# is a palindrome
def isPalindrome(s, i, j) :
     
    while (i < j) :
         
        if (s[i] != s[j]) :
            return False;
             
        i += 1;
        j -= 1;
 
    return True;
 
# Function to get the required index
def getIndex(s1, s2, length) :
     
    i = 0 ; j = length - 1;
 
    # Start comparing the two strings
    # from both ends.
    while (i < j) :
         
        # Break from the loop at first mismatch
        if (s1[i] != s2[j]) :
            break;
 
        i += 1;
        j -= 1;
 
    # If it is possible to concatenate
    # the strings to form palindrome,
    # return index
    if (i == j) :
        return i - 1;
 
    # If remaining part for s2
    # is palindrome
    elif (isPalindrome(s2, i, j)) :
        return i - 1;
 
    # If remaining part for s1
    # is palindrome
    elif (isPalindrome(s1, i, j)) :
        return j;
 
    # If not possible, return -1
    return -1;
 
# Driver Code
if __name__ == "__main__" :
 
    s1 = "abcdf" ;
    s2 = "sfgba";
    length = len(s1) ;
 
    print(getIndex(s1, s2, length));
     
# This code is contributed by Ryuga

C#

// C# implementation of the above approach
using System;
 
class GFG
{
 
// Function that returns true if the sub-String
// starting from index i and ending at index j
// is a palindrome
static bool isPalindrome(string s,
                         int i, int j)
{
    while (i < j)
    {
        if (s[i] != s[j])
 
            return false;
        i++;
        j--;
    }
    return true;
}
 
// Function to get the required index
static int getIndex(string s1, string s2, int len)
{
    int i = 0, j = len - 1;
 
    // Start comparing the two Strings
    // from both ends.
    while (i < j)
    {
        // Break from the loop at first
        // mismatch
        if (s1[i] != s2[j])
        {
            break;
        }
 
        i++;
        j--;
    }
 
    // If it is possible to concatenate
    // the Strings to form palindrome,
    // return index
    if (i == j)
    {
        return i - 1;
    }
 
    // If remaining part for s2
    // is palindrome
    else if (isPalindrome(s2, i, j))
        return i - 1;
 
    // If remaining part for s1
    // is palindrome
    else if (isPalindrome(s1, i, j))
        return j;
 
    // If not possible, return -1
    return -1;
}
 
// Driver Code
public static void Main()
{
    string s1 = "abcdf", s2 = "sfgba";
    int len = s1.Length;
 
    Console.WriteLine(getIndex(s1, s2, len));
 
}
}
 
// This code is contributed by Code_Mech.

Javascript

<script>
 
    // JavaScript implementation of the above approach
     
    // Function that returns true if the sub-String
    // starting from index i and ending at index j
    // is a palindrome
    function isPalindrome(s, i, j)
    {
        while (i < j)
        {
            if (s[i] != s[j])
 
                return false;
            i++;
            j--;
        }
        return true;
    }
 
    // Function to get the required index
    function getIndex(s1, s2, len)
    {
        let i = 0, j = len - 1;
 
        // Start comparing the two Strings
        // from both ends.
        while (i < j)
        {
            // Break from the loop at first
            // mismatch
            if (s1[i] != s2[j])
            {
                break;
            }
 
            i++;
            j--;
        }
 
        // If it is possible to concatenate
        // the Strings to form palindrome,
        // return index
        if (i == j)
        {
            return i - 1;
        }
 
        // If remaining part for s2
        // is palindrome
        else if (isPalindrome(s2, i, j))
            return i - 1;
 
        // If remaining part for s1
        // is palindrome
        else if (isPalindrome(s1, i, j))
            return j;
 
        // If not possible, return -1
        return -1;
    }
     
    let s1 = "abcdf", s2 = "sfgba";
    let len = s1.length;
  
    document.write(getIndex(s1, s2, len) + "</br>");
 
</script>
Producción: 

1

 

Complejidad de tiempo : O(N), donde N es la longitud de la string.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *