Dada una string, comprueba si se trata de una rotación de un palíndromo. Por ejemplo, su función debería devolver verdadero para «aab», ya que es una rotación de «aba».
Ejemplos:
Input: str = "aaaad" Output: 1 // "aaaad" is a rotation of a palindrome "aadaa" Input: str = "abcd" Output: 0 // "abcd" is not a rotation of any palindrome.
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Una solución simple es tomar la string de entrada, probar todas las rotaciones posibles y devolver verdadero si una rotación es un palíndromo. Si ninguna rotación es palíndromo, devuelve falso.
A continuación se muestra la implementación de este enfoque.
Implementación:
C++
#include <iostream>
#include <string>
using namespace std;
// A utility function to check if a string str is palindrome
bool isPalindrome(string str)
{
// Start from leftmost and rightmost corners of str
int l = 0;
int h = str.length() - 1;
// Keep comparing characters while they are same
while (h > l)
if (str[l++] != str[h--])
return false;
// If we reach here, then all characters were matching
return true;
}
// Function to check if a given string is a rotation of a
// palindrome.
bool isRotationOfPalindrome(string str)
{
// If string itself is palindrome
if (isPalindrome(str))
return true;
// Now try all rotations one by one
int n = str.length();
for (int i = 0; i < n - 1; i++) {
string str1 = str.substr(i + 1, n - i - 1);
string str2 = str.substr(0, i + 1);
// Check if this rotation is palindrome
if (isPalindrome(str1.append(str2)))
return true;
}
return false;
}
// Driver program to test above function
int main()
{
cout << isRotationOfPalindrome("aab") << endl;
cout << isRotationOfPalindrome("abcde") << endl;
cout << isRotationOfPalindrome("aaaad") << endl;
return 0;
}
Java
// Java program to check if a given string
// is a rotation of a palindrome
import java.io.*;
class Palindrome {
// A utility function to check if a string str is palindrome
static boolean isPalindrome(String str)
{
// Start from leftmost and rightmost corners of str
int l = 0;
int h = str.length() - 1;
// Keep comparing characters while they are same
while (h > l)
if (str.charAt(l++) != str.charAt(h--))
return false;
// If we reach here, then all characters were matching
return true;
}
// Function to check if a given string is a rotation of a
// palindrome
static boolean isRotationOfPalindrome(String str)
{
// If string itself is palindrome
if (isPalindrome(str))
return true;
// Now try all rotations one by one
int n = str.length();
for (int i = 0; i < n - 1; i++) {
String str1 = str.substring(i + 1);
String str2 = str.substring(0, i + 1);
// Check if this rotation is palindrome
if (isPalindrome(str1 + str2))
return true;
}
return false;
}
// driver program
public static void main(String[] args)
{
System.out.println((isRotationOfPalindrome("aab")) ? 1 : 0);
System.out.println((isRotationOfPalindrome("abcde")) ? 1 : 0);
System.out.println((isRotationOfPalindrome("aaaad")) ? 1 : 0);
}
}
// Contributed by Pramod Kumar
Python3
# Python program to check if a given string is a rotation
# of a palindrome
# A utility function to check if a string str is palindrome
def isPalindrome(string):
# Start from leftmost and rightmost corners of str
l = 0
h = len(string) - 1
# Keep comparing characters while they are same
while h > l:
l+= 1
h-= 1
if string[l-1] != string[h + 1]:
return False
# If we reach here, then all characters were matching
return True
# Function to check if a given string is a rotation of a
# palindrome.
def isRotationOfPalindrome(string):
# If string itself is palindrome
if isPalindrome(string):
return True
# Now try all rotations one by one
n = len(string)
for i in range(n-1):
string1 = string[i + 1:n]
string2 = string[0:i + 1]
# Check if this rotation is palindrome
string1+=(string2)
if isPalindrome(string1):
return True
return False
# Driver program
print ("1" if isRotationOfPalindrome("aab") == True else "0")
print ("1" if isRotationOfPalindrome("abcde") == True else "0")
print ("1" if isRotationOfPalindrome("aaaad") == True else "0")
# This code is contributed by BHAVYA JAIN
C#
// C# program to check if a given string
// is a rotation of a palindrome
using System;
class GFG {
// A utility function to check if
// a string str is palindrome
public static bool isPalindrome(string str)
{
// Start from leftmost and
// rightmost corners of str
int l = 0;
int h = str.Length - 1;
// Keep comparing characters
// while they are same
while (h > l) {
if (str[l++] != str[h--]) {
return false;
}
}
// If we reach here, then all
// characters were matching
return true;
}
// Function to check if a given string
// is a rotation of a palindrome
public static bool isRotationOfPalindrome(string str)
{
// If string itself is palindrome
if (isPalindrome(str)) {
return true;
}
// Now try all rotations one by one
int n = str.Length;
for (int i = 0; i < n - 1; i++) {
string str1 = str.Substring(i + 1);
string str2 = str.Substring(0, i + 1);
// Check if this rotation is palindrome
if (isPalindrome(str1 + str2)) {
return true;
}
}
return false;
}
// Driver Code
public static void Main(string[] args)
{
Console.WriteLine((isRotationOfPalindrome("aab")) ? 1 : 0);
Console.WriteLine((isRotationOfPalindrome("abcde")) ? 1 : 0);
Console.WriteLine((isRotationOfPalindrome("aaaad")) ? 1 : 0);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// javascript program to check if a given string
// is a rotation of a palindrome
// A utility function to check if
// a string str is palindrome
function isPalindrome( str)
{
// Start from leftmost and
// rightmost corners of str
var l = 0;
var h = str.length - 1;
// Keep comparing characters
// while they are same
while (h > l) {
if (str[l++] != str[h--]) {
return false;
}
}
// If we reach here, then all
// characters were matching
return true;
}
// Function to check if a given string
// is a rotation of a palindrome
function isRotationOfPalindrome( str)
{
// If string itself is palindrome
if (isPalindrome(str)) {
return true;
}
// Now try all rotations one by one
var n = str.length;
for (var i = 0; i < n - 1; i++) {
var str1 = str.substring(i + 1);
var str2 = str.substring(0, i + 1);
// Check if this rotation is palindrome
if (isPalindrome(str1 + str2)) {
return true;
}
}
return false;
}
// Driver Code
document.write((isRotationOfPalindrome("aab")) ? 1 : 0 );
document.write("<br>");
document.write((isRotationOfPalindrome("abcde")) ? 1 : 0 );
document.write("<br>");
document.write((isRotationOfPalindrome("aaaad")) ? 1 : 0);
// This code is contributed by bunnyram19.
</script>
Producción
1 0 1
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n) para almacenar rotaciones.
Tenga en cuenta que el algoritmo anterior se puede optimizar para que funcione en O(1) espacio adicional, ya que podemos rotar una string en O(n) tiempo y O(1) espacio adicional .
Una solución optimizada puede funcionar en tiempo O(n). La idea aquí es usar el algoritmo de Manacher para resolver el problema anterior.
- Deje que la string dada sea ‘s’ y la longitud de la string sea ‘n’.
- Preprocesar/Preparar la string para usar el Algoritmo de Manachers, para ayudar a encontrar un palíndromo de longitud uniforme, para lo cual concatenamos la string dada consigo misma (para encontrar si la rotación dará un palíndromo) y agregamos el símbolo ‘$’ al principio y los caracteres ‘#’ entre letras. Terminamos la string usando ‘@’. Entonces, para la entrada ‘aaad’, la string reformada será: ‘$#a#a#a#a#d#a#a#a#a#d#@’
- Ahora el problema se reduce a encontrar la substring palindrómica más larga usando el algoritmo de Manacher de longitud n o mayor en la string.
- Si hay una substring palindrómica de longitud n, devuelve verdadero, de lo contrario, devuelve falso. Si encontramos un palíndromo de mayor longitud, verificamos si el tamaño de nuestra entrada es par o impar, en consecuencia, la longitud de nuestro palíndromo encontrado también debe ser par o impar.
Por ej. si nuestro tamaño de entrada es 3 y mientras realizamos el Algoritmo de Manacher obtenemos un palíndromo de tamaño 5, obviamente contendría una substring de tamaño 3 que es un palíndromo, pero no se puede decir lo mismo de un palíndromo de longitud 4. Por lo tanto, verificamos si tanto el tamaño de la entrada como el tamaño del palíndromo encontrado en cualquier instancia son pares o impares.
El caso límite sería una palabra con las mismas letras que desafiaría la propiedad anterior, pero para ese caso nuestro algoritmo encontrará palíndromos de longitud par e impar, uno de ellos es una substring, por lo tanto, no será un problema.
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if we have found
// a palindrome of same length as the input
// which is a rotation of the input string
bool checkPal(int x, int len)
{
if (x == len)
return true;
else if (x > len) {
if ((x % 2 == 0 && len % 2 == 0)
|| (x % 2 != 0 && len % 2 != 0))
return true;
}
return false;
}
// Function to preprocess the string
// for Manacher's Algorithm
string reform(string s)
{
string s1 = "$#";
// Adding # between the characters
for (int i = 0; i < s.size(); i++) {
s1 += s[i];
s1 += '#';
}
s1 += '@';
return s1;
}
// Function to find the longest palindromic
// substring using Manacher's Algorithm
bool longestPal(string s, int len)
{
// Current Left Position
int mirror = 0;
// Center Right Position
int R = 0;
// Center Position
int C = 0;
// LPS Length Array
int P[s.size()] = { 0 };
int x = 0;
// Get currentLeftPosition Mirror
// for currentRightPosition i
for (int i = 1; i < s.size() - 1; i++) {
mirror = 2 * C - i;
// If currentRightPosition i is
// within centerRightPosition R
if (i < R)
P[i] = min((R - i), P[mirror]);
// Attempt to expand palindrome centered
// at currentRightPosition i
while (s[i + (1 + P[i])] == s[i - (1 + P[i])]) {
P[i]++;
}
// Check for palindrome
bool ans = checkPal(P[i], len);
if (ans)
return true;
// If palindrome centered at currentRightPosition i
// expand beyond centerRightPosition R,
// adjust centerPosition C based on expanded palindrome
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
return false;
}
// Driver code
int main()
{
string s = "aaaad";
int len = s.size();
s += s;
s = reform(s);
cout << longestPal(s, len);
return 0;
}
// This code is contributed by Vindusha Pankajakshan
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to check if we have found
// a palindrome of same length as the input
// which is a rotation of the input string
static boolean checkPal(int x, int len)
{
if (x == len)
{
return true;
}
else if (x > len)
{
if ((x % 2 == 0 && len % 2 == 0) ||
(x % 2 != 0 && len % 2 != 0))
{
return true;
}
}
return false;
}
// Function to preprocess the string
// for Manacher's Algorithm
static String reform(String s)
{
String s1 = "$#";
// Adding # between the characters
for (int i = 0; i < s.length(); i++)
{
s1 += s.charAt(i);
s1 += '#';
}
s1 += '@';
return s1;
}
// Function to find the longest palindromic
// substring using Manacher's Algorithm
static boolean longestPal(String s, int len)
{
// Current Left Position
int mirror = 0;
// Center Right Position
int R = 0;
// Center Position
int C = 0;
// LPS Length Array
int[] P = new int[s.length()];
int x = 0;
// Get currentLeftPosition Mirror
// for currentRightPosition i
for (int i = 1; i < s.length() - 1; i++)
{
mirror = 2 * C - i;
// If currentRightPosition i is
// within centerRightPosition R
if (i < R)
{
P[i] = Math.min((R - i), P[mirror]);
}
// Attempt to expand palindrome centered
// at currentRightPosition i
while (s.charAt(i + (1 + P[i])) ==
s.charAt(i - (1 + P[i])))
{
P[i]++;
}
// Check for palindrome
boolean ans = checkPal(P[i], len);
if (ans)
{
return true;
}
// If palindrome centered at currentRightPosition i
// expand beyond centerRightPosition R,
// adjust centerPosition C based on expanded palindrome
if (i + P[i] > R)
{
C = i;
R = i + P[i];
}
}
return false;
}
// Driver code
public static void main(String[] args)
{
String s = "aaaad";
int len = s.length();
s += s;
s = reform(s);
System.out.println(longestPal(s, len) ? 1 : 0);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python implementation of the approach # Function to check if we have found # a palindrome of same length as the input # which is a rotation of the input string def checkPal (x, Len): if (x == Len): return True elif (x > Len): if ((x % 2 == 0 and Len % 2 == 0) or (x % 2 != 0 and Len % 2 != 0)): return True return False # Function to preprocess the string # for Manacher's Algorithm def reform (s): s1 = "$#" # Adding '#' between the characters for i in range(len(s)): s1 += s[i] s1 += "#" s1 += "@" return s1 # Function to find the longest palindromic # substring using Manacher's Algorithm def longestPal (s, Len): # Current Left Position mirror = 0 # Center Right Position R = 0 # Center Position C = 0 # LPS Length Array P = [0] * len(s) x = 0 # Get currentLeftPosition Mirror # for currentRightPosition i for i in range(1, len(s) - 1): mirror = 2 * C - i # If currentRightPosition i is # within centerRightPosition R if (i < R): P[i] = min((R-i), P[mirror]) # Attempt to expand palindrome centered # at currentRightPosition i while (s[i + (1 + P[i])] == s[i - (1 + P[i])]): P[i] += 1 # Check for palindrome ans = checkPal(P[i], Len) if (ans): return True # If palindrome centered at current # RightPosition i expand beyond # centerRightPosition R, adjust centerPosition # C based on expanded palindrome if (i + P[i] > R): C = i R = i + P[i] return False # Driver Code if __name__ == '__main__': s = "aaaad" Len = len(s) s += s s = reform(s) print(longestPal(s, Len)) # This code is contributed by himanshu77
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if we have found
// a palindrome of same length as the input
// which is a rotation of the input string
static bool checkPal(int x, int len)
{
if (x == len)
{
return true;
}
else if (x > len)
{
if ((x % 2 == 0 && len % 2 == 0) ||
(x % 2 != 0 && len % 2 != 0))
{
return true;
}
}
return false;
}
// Function to preprocess the string
// for Manacher's Algorithm
static String reform(String s)
{
String s1 = "$#";
// Adding # between the characters
for (int i = 0; i < s.Length; i++)
{
s1 += s[i];
s1 += '#';
}
s1 += '@';
return s1;
}
// Function to find the longest palindromic
// substring using Manacher's Algorithm
static bool longestPal(String s, int len)
{
// Current Left Position
int mirror = 0;
// Center Right Position
int R = 0;
// Center Position
int C = 0;
// LPS Length Array
int[] P = new int[s.Length];
int x = 0;
// Get currentLeftPosition Mirror
// for currentRightPosition i
for (int i = 1; i < s.Length - 1; i++)
{
mirror = 2 * C - i;
// If currentRightPosition i is
// within centerRightPosition R
if (i < R)
{
P[i] = Math.Min((R - i), P[mirror]);
}
// Attempt to expand palindrome centered
// at currentRightPosition i
while (s[i + (1 + P[i])] == s[i - (1 + P[i])])
{
P[i]++;
}
// Check for palindrome
bool ans = checkPal(P[i], len);
if (ans)
{
return true;
}
// If palindrome centered at currentRightPosition i
// expand beyond centerRightPosition R,
// adjust centerPosition C based on expanded palindrome
if (i + P[i] > R)
{
C = i;
R = i + P[i];
}
}
return false;
}
// Driver code
public static void Main(String[] args)
{
String s = "aaaad";
int len = s.Length;
s += s;
s = reform(s);
Console.WriteLine(longestPal(s, len) ? 1 : 0);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation of the approach
// Function to check if we have found
// a palindrome of same length as the input
// which is a rotation of the input string
function checkPal(x , len) {
if (x == len) {
return true;
} else if (x > len) {
if ((x % 2 == 0 && len % 2 == 0) ||
(x % 2 != 0 && len % 2 != 0))
{
return true;
}
}
return false;
}
// Function to preprocess the string
// for Manacher's Algorithm
function reform( s) {
var s1 = "$#";
// Adding # between the characters
for (i = 0; i < s.length; i++) {
s1 += s.charAt(i);
s1 += '#';
}
s1 += '@';
return s1;
}
// Function to find the longest palindromic
// substring using Manacher's Algorithm
function longestPal( s , len) {
// Current Left Position
var mirror = 0;
// Center Right Position
var R = 0;
// Center Position
var C = 0;
// LPS Length Array
var P = Array(s.length).fill(0);
var x = 0;
// Get currentLeftPosition Mirror
// for currentRightPosition i
for (i = 1; i < s.length - 1; i++) {
mirror = 2 * C - i;
// If currentRightPosition i is
// within centerRightPosition R
if (i < R) {
P[i] = Math.min((R - i), P[mirror]);
}
// Attempt to expand palindrome centered
// at currentRightPosition i
while (s.charAt(i + (1 + P[i])) == s.charAt(i - (1 + P[i]))) {
P[i]++;
}
// Check for palindrome
var ans = checkPal(P[i], len);
if (ans) {
return true;
}
// If palindrome centered at currentRightPosition i
// expand beyond centerRightPosition R,
// adjust centerPosition C based on expanded palindrome
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
return false;
}
// Driver code
var s = "aaaad";
var len = s.length;
s += s;
s = reform(s);
document.write(longestPal(s, len) ? 1 : 0);
// This code is contributed by umadevi9616
</script>
Producción
1
Complejidad del tiempo : O(n 2 )
Espacio Auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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