Dadas dos strings a y b de la misma longitud, la tarea es verificar si dividir ambas strings y concatenar sus substrings opuestas, es decir, concatenar la substring izquierda de a con la substring derecha de b o concatenar la substring izquierda de b con la substring derecha de a , forma un palíndromo o no . Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Nota: una de las substrings divididas puede estar vacía.
Ejemplos:
Entrada: a = “x”, b = “y”
Salida: Sí
Explicación:
Divida ambas strings en el índice 0.
Substring izquierda de a (aLeft) = ” “, Substring derecha de a (aRight) = “x” Substring
izquierda de b (bIzquierda) = ” “, Substring derecha de b (bDerecha) = “y”
Dado que aIzquierda + bDerecha = ” ” + “y” = “y”, que es un palíndromo al igual que bIzquierda + aDerecha= ” ” + “x” = “x” también es un palíndromo, escribe Sí.Entrada: a = “ulacfd”, b = “jizalu”
Salida: Verdadero
Explicación:
Dividir ambas strings en el índice 3:
Substring izquierda de a (aLeft) = “ula”, Substring derecha de a (aRight) = “cfd”
, Substring izquierda de b (bLeft) = “jiz”, Substring derecha de b (bRight) = “alu”
Dado que aleft + bright = “ula” + “alu” = “ulaalu”, que es un palíndromo, imprime Sí.
Enfoque: La idea es utilizar la técnica Two Pointer para resolver este problema. Siga los pasos a continuación para resolver el problema:
- Coloque un puntero i en el índice 0 de a y «j» en el último índice de b .
- Itere sobre los caracteres de la string y verifique si a[i] == b[j] , luego incremente i y disminuya j .
- De lo contrario, simplemente rompa el ciclo ya que no es una secuencia de tipo palíndromo.
- Concatene aLeft y bRight en una variable de string xa y aRight y bLeft en otra variable de string xb .
- Compruebe si alguna de las dos strings es un palíndromo o no. Si es cierto, escriba “Sí” . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if concatenating // opposite substrings after splitting // two given strings forms a palindrome // or not bool checkSplitting(string a, string b) { // Length of the string int len = a.length(); int i = 0, j = len - 1; // Iterate through the strings while (i < len) { // If not a palindrome sequence if (a[i] != b[j]) { break; } i += 1; j -= 1; // Concatenate left substring of a // and right substring of b in xa // Concatenate right substring of a // and left substring of b in xb string xa = a.substr(i, j + 1); string xb = b.substr(i, j + 1); // Check if either of the two concatenated // strings is a palindrome or not if (xa == string(xa.rbegin(), xa.rend()) || xb == string(xb.rbegin(), xb.rend())) return true; } } // Function to check if concatenation of splitted // substrings of two given strings forms a palindrome void isSplitPossible(string a, string b) { if (checkSplitting(a, b) == true) { cout << "Yes"; } else if (checkSplitting(b, a) == true) { cout << "Yes"; } else { cout << "No"; } } // Driver Code int main() { string a = "ulacfd", b = "jizalu"; // Function Call isSplitPossible(a, b); return 0; } // This code is contributed by pushpendrayadav1057
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if concatenating // opposite subStrings after splitting // two given Strings forms a palindrome // or not static boolean checkSplitting(String a, String b) { // Length of the String int len = a.length(); int i = 0, j = len - 1; // Iterate through the Strings while (i < len) { // If not a palindrome sequence if (a.charAt(i) != b.charAt(j)) { break; } i += 1; j -= 1; // Concatenate left subString of a // and right subString of b in xa // Concatenate right subString of a // and left subString of b in xb String xa = a.substring(i, j + 1); String xb = b.substring(i, j + 1); // Check if either of the two concatenated // Strings is a palindrome or not if (xa.equals(reverse(xa))||xb.equals(reverse(xb))) return true; } return false; } // Function to check if concatenation of splitted // subStrings of two given Strings forms a palindrome static void isSplitPossible(String a, String b) { if (checkSplitting(a, b) == true) { System.out.print("Yes"); } else if (checkSplitting(b, a) == true) { System.out.print("Yes"); } else { System.out.print("No"); } } static String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a); } // Driver Code public static void main(String[] args) { String a = "ulacfd", b = "jizalu"; // Function Call isSplitPossible(a, b); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to check if concatenating # opposite substrings after splitting # two given strings forms a palindrome or not def checkSplitting(a, b, n): i, j = 0, n - 1 # Iterate through the strings while(i < n): # If not a palindrome sequence if(a[i] != b[j]): break i += 1 j -= 1 # Concatenate left substring of a # and right substring of b in xa # Concatenate right substring of a # and left substring of b in xb xa = a[i:j + 1] xb = b[i:j + 1] # Check if either of the two concatenated # strings is a palindrome or not if(xa == xa[::-1] or xb == xb[::-1]): return True # Function to check if concatenation of splitted # substrings of two given strings forms a palindrome def isSplitPossible(a, b): if checkSplitting(a, b, len(a)) == True: print("Yes") elif checkSplitting(b, a, len(a)) == True: print("Yes") else: print("No") # Given string a and b a = "ulacfd" b = "jizalu" # Function Call isSplitPossible(a, b)
C#
// C# program for the above approach using System; class GFG{ // Function to check if concatenating // opposite subStrings after splitting // two given Strings forms a palindrome // or not static bool checkSplitting(String a, String b) { // Length of the String int len = a.Length; int i = 0, j = len - 1; // Iterate through the Strings while (i < len) { // If not a palindrome sequence if (a[i] != b[j]) { break; } i += 1; j -= 1; // Concatenate left subString of a // and right subString of b in xa // Concatenate right subString of a // and left subString of b in xb String xa = a.Substring(i, j + 1 - i); String xb = b.Substring(i, j + 1 - i); // Check if either of the two concatenated // Strings is a palindrome or not if (xa.Equals(reverse(xa)) || xb.Equals(reverse(xb))) return true; } return false; } // Function to check if concatenation of splitted // subStrings of two given Strings forms a palindrome static void isSplitPossible(String a, String b) { if (checkSplitting(a, b) == true) { Console.Write("Yes"); } else if (checkSplitting(b, a) == true) { Console.Write("Yes"); } else { Console.Write("No"); } } static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("",a); } // Driver Code public static void Main(String[] args) { String a = "ulacfd", b = "jizalu"; // Function Call isSplitPossible(a, b); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program for the above approach // Function to check if the string is palindrome or not function checkPalindrome(str) { // find the length of a string var len = str.length; // loop through half of the string for (var i = 0; i < parseInt(len / 2); i++) { // check if first and last string are same if (str[i] !== str[len - 1 - i]) { return false; } } return true; } // Function to check if concatenating // opposite substrings after splitting // two given strings forms a palindrome // or not function checkSplitting(a, b) { // Length of the string var len = a.length; var i = 0, j = len - 1; // Iterate through the strings while (i < len) { // If not a palindrome sequence if (a[i] != b[j]) { break; } i += 1; j -= 1; // Concatenate left substring of a // and right substring of b in xa // Concatenate right substring of a // and left substring of b in xb var xa = a.substring(i, j + 1); var xb = b.substring(i, j + 1); // Check if either of the two concatenated // strings is a palindrome or not if (checkPalindrome(xa)==true || checkPalindrome(xb)==true) return true; } } // Function to check if concatenation of splitted // substrings of two given strings forms a palindrome function isSplitPossible(a, b) { if (checkSplitting(a, b) == true) { document.write( "Yes"); } else if (checkSplitting(b, a) == true) { document.write("Yes"); } else { document.write( "No"); } } var a = "ulacfd", b = "jizalu"; // Function Call isSplitPossible(a, b); // This code is contributed by SoumikMondal </script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA