Comprobar si una string dada es una rotación de un palíndromo

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:

#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 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

# 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# 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

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

1
0
1

Complejidad de Tiempo: O(n ² ) 
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++ 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 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

# 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# 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

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

1

Complejidad del tiempo : O(n ² )

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.