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: 1
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