Рубрики

Проверьте, является ли данная строка вращением палиндрома

По заданной строке проверьте, является ли она вращением палиндрома. Например, ваша функция должна возвращать true для «aab», поскольку это вращение «aba».

Примеры:

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.

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Простое решение состоит в том, чтобы взять входную строку, попробовать каждое возможное ее вращение и вернуть true, если вращение является палиндромом. Если нет вращения палиндромом, верните false.
Ниже приводится реализация этого подхода.

C ++

#include <iostream>
#include <string>

using namespace std;

  
// Утилита для проверки, является ли строка str палиндромом

bool isPalindrome(string str)

{

    // Начинаем с самого левого и правого углов str

    int l = 0;

    int h = str.length() - 1;

  

    // Продолжаем сравнивать символы, пока они одинаковые

    while (h > l)

        if (str[l++] != str[h--])

            return false;

  

    // Если мы дойдем до здесь, то все символы будут соответствовать

    return true;

}

  
// Функция для проверки, является ли данная строка вращением
// палиндром.

bool isRotationOfPalindrome(string str)

{

    // Если строка iteself является палиндромом

    if (isPalindrome(str))

        return true;

  

    // Теперь попробуйте все повороты один за другим

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

  

        // Проверяем, является ли это вращение палиндромом

        if (isPalindrome(str1.append(str2)))

            return true;

    }

    return false;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    cout << isRotationOfPalindrome("aab") << endl;

    cout << isRotationOfPalindrome("abcde") << endl;

    cout << isRotationOfPalindrome("aaaad") << endl;

    return 0;

}

Джава

// Java программа для проверки наличия заданной строки
// вращение палиндрома

import java.io.*;

  

class Palindrome {

    // Утилита для проверки, является ли строка str палиндромом

    static boolean isPalindrome(String str)

    {

        // Начинаем с самого левого и правого углов str

        int l = 0;

        int h = str.length() - 1;

  

        // Продолжаем сравнивать символы, пока они одинаковые

        while (h > l)

            if (str.charAt(l++) != str.charAt(h--))

                return false;

  

        // Если мы дойдем до здесь, то все символы будут соответствовать

        return true;

    }

  

    // Функция для проверки, является ли данная строка вращением

    // палиндром

    static boolean isRotationOfPalindrome(String str)

    {

        // Если строка iteself является палиндромом

        if (isPalindrome(str))

            return true;

  

        // Теперь попробуйте все повороты один за другим

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

  

            // Проверяем, является ли это вращение палиндромом

            if (isPalindrome(str1 + str2))

                return true;

        }

        return false;

    }

  

    // драйверная программа

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

    }

}

  
// Предоставлено Прамод Кумар

питон

# Программа Python, чтобы проверить, является ли данная строка вращением
# палиндрома

  
# Полезная функция для проверки, является ли строка str палиндромом

def isPalindrome(string):

  

    # Начните с самого левого и правого углов ул.

    l = 0

    h = len(string) - 1

  

    # Продолжайте сравнивать персонажей, пока они одинаковы

    while h > l:

        l+= 1

        h-= 1

        if string[l-1] != string[h + 1]:

            return False

  

    # Если мы дойдем до здесь, то все персонажи совпадают

    return True

  
# Функция, чтобы проверить, является ли данная строка вращением
# палиндром.

def isRotationOfPalindrome(string):

  

    # Если строка сама по себе является палиндромом

    if isPalindrome(string):

        return True

  

    # Теперь попробуйте все повороты по одному

    n = len(string)

    for i in xrange(n-1):

        string1 = string[i + 1:n]

        string2 = string[0:i + 1]

  

        # Проверьте, является ли это вращение палиндромом

        string1+=(string2)

        if isPalindrome(string1):

            return True

  

    return False

  
# Драйверная программа

print "1" if isRotationOfPalindrome("aab") == True else "0"

print "1" if isRotationOfPalindrome("abcde") == True else "0"

print "1" if isRotationOfPalindrome("aaaad") == True else "0"

  
# Этот код предоставлен BHAVYA JAIN

C #

// C # программа для проверки наличия заданной строки
// вращение палиндрома

using System;

  

class GFG {

    // Полезная функция для проверки

    // строка является палиндромом

    public static bool isPalindrome(string str)

    {

        // Начнем с самого левого и

        // самые правые углы ул

        int l = 0;

        int h = str.Length - 1;

  

        // Продолжаем сравнивать символы

        // пока они одинаковые

        while (h > l) {

            if (str[l++] != str[h--]) {

                return false;

            }

        }

  

        // Если мы доберемся сюда, то все

        // символы совпадают

        return true;

    }

  

    // Функция для проверки наличия заданной строки

    // вращение палиндрома

    public static bool isRotationOfPalindrome(string str)

    {

        // Если строка iteself является палиндромом

        if (isPalindrome(str)) {

            return true;

        }

  

        // Теперь попробуйте все повороты один за другим

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

  

            // Проверяем, является ли это вращение палиндромом

            if (isPalindrome(str1 + str2)) {

                return true;

            }

        }

        return false;

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

        Console.WriteLine((isRotationOfPalindrome("aab")) ? 1 : 0);

        Console.WriteLine((isRotationOfPalindrome("abcde")) ? 1 : 0);

        Console.WriteLine((isRotationOfPalindrome("aaaad")) ? 1 : 0);

    }

}

  
// Этот код предоставлен Shrikant13


Выход:

1
0
1

Сложность времени: O (n 2 )
Вспомогательное пространство: O (n) для хранения вращений.
Обратите внимание, что приведенный выше алгоритм может быть оптимизирован для работы в O (1) дополнительном пространстве, так как мы можем вращать строку за O (n) времени и O (1) в дополнительном пространстве .

Оптимизированное решение может работать за O (n) времени. Идея здесь состоит в том, чтобы использовать алгоритм Манахера для решения вышеуказанной проблемы.

  • Пусть заданная строка будет 's', а длина строки будет 'n'.
  • Предварительная обработка / подготовка строки для использования алгоритма Manachers, чтобы помочь найти палиндром четной длины, для которого мы объединяем данную строку с самим собой (чтобы найти, будет ли вращение давать палиндром) и добавляем символ «$» в начале и символы «#» между буквами. Мы заканчиваем строку, используя '@'. Таким образом, для ввода 'aaad' измененная строка будет выглядеть так: '$ # a # a # a # a # d # a # a # a # a # d # @'
  • Теперь проблема сводится к тому, чтобы найти самую длинную палиндромную подстроку, используя алгоритм Манахера длиной n или больше в строке.
  • Если есть палиндромная подстрока длины n, вернуть true, иначе вернуть false. Если мы находим палиндром большей длины, то мы проверяем, является ли размер нашего ввода четным или нечетным, соответственно, наша найденная длина палиндрома также должна быть четной или нечетной.

Например, если наш входной размер равен 3 и при выполнении алгоритма Manacher мы получаем палиндром размером 5, он, очевидно, будет содержать подстроку размера 3, которая является палиндромом, но этого нельзя сказать для палиндрома длины 4. Следовательно, мы проверяем, и размер входного сигнала, и размер палиндрома, найденного в любом случае, являются как четными, так и нечетными.

Граничным регистром будет слово с теми же буквами, которое не поддается описанному выше свойству, но в этом случае наш алгоритм найдет палиндром как четной, так и нечетной длины, одна из которых является подстрокой, поэтому это не будет проблемой.

Ниже приведена реализация вышеуказанного алгоритма:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для проверки, если мы нашли
// палиндром той же длины, что и вход
// который является вращением входной строки

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;

}

  
// Функция для предварительной обработки строки
// для алгоритма Манахера
string reform(string s)
{

    string s1 = "$#";

  

    // Добавляем # между символами

    for (int i = 0; i < s.size(); i++) {

        s1 += s[i];

        s1 += '#';

    }

  

    s1 += '@';

    return s1;

}

  
// Функция для поиска самого длинного палиндрома
// подстрока с использованием алгоритма Манахера

bool longestPal(string s, int len)

{

  

    // Текущая левая позиция

    int mirror = 0;

  

    // Правая позиция по центру

    int R = 0;

  

    // Центральная позиция

    int C = 0;

  

    // LPS Length Array

    int P[s.size()] = { 0 };

    int x = 0;

  

    // Получить currentLeftPosition Mirror

    // для currentRightPosition i

    for (int i = 1; i < s.size() - 1; i++) {

        mirror = 2 * C - i;

  

        // Если currentRightPosition i

        // в пределах centerRightPosition R

        if (i < R)

            P[i] = min((R - i), P[mirror]);

  

        // Попытка расширить палиндром по центру

        // at currentRightPosition i

        while (s[i + (1 + P[i])] == s[i - (1 + P[i])]) {

            P[i]++;

        }

  

        // Проверка на палиндром

        bool ans = checkPal(P[i], len);

        if (ans)

            return true;

  

        // Если палиндром центрирован на currentRightPosition i

        // расширить за пределы centerRightPosition R,

        // настраиваем centerPosition C на основе расширенного палиндрома

        if (i + P[i] > R) {

            C = i;

            R = i + P[i];

        }

    }

  

    return false;

}

  
// Код драйвера

int main()

{

    string s = "aaaad";

    int len = s.size();

    s += s;

    s = reform(s);

    cout << longestPal(s, len);

  

    return 0;

}

  
// Этот код предоставлен Виндушей Панкаджакшаном

Джава

// Java реализация подхода

import java.util.*;

  

class GFG 

{

  
// Функция для проверки, если мы нашли
// палиндром той же длины, что и вход
// который является вращением входной строки

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;

}

  
// Функция для предварительной обработки строки
// для алгоритма Манахера

static String reform(String s)

{

    String s1 = "$#";

  

    // Добавляем # между символами

    for (int i = 0; i < s.length(); i++) 

    {

        s1 += s.charAt(i);

        s1 += '#';

    }

  

    s1 += '@';

    return s1;

}

  
// Функция для поиска самого длинного палиндрома
// подстрока с использованием алгоритма Манахера

static boolean longestPal(String s, int len) 

{

  

    // Текущая левая позиция

    int mirror = 0;

  

    // Правая позиция по центру

    int R = 0;

  

    // Центральная позиция

    int C = 0;

  

    // LPS Length Array

    int[] P = new int[s.length()];

    int x = 0;

  

    // Получить currentLeftPosition Mirror

    // для currentRightPosition i

    for (int i = 1; i < s.length() - 1; i++)

    {

        mirror = 2 * C - i;

  

        // Если currentRightPosition i

        // в пределах centerRightPosition R

        if (i < R) 

        {

            P[i] = Math.min((R - i), P[mirror]);

        }

  

        // Попытка расширить палиндром по центру

        // at currentRightPosition i

        while (s.charAt(i + (1 + P[i])) == 

               s.charAt(i - (1 + P[i])))

        {

            P[i]++;

        }

  

        // Проверка на палиндром

        boolean ans = checkPal(P[i], len);

        if (ans) 

        {

            return true;

        }

  

        // Если палиндром центрирован на currentRightPosition i

        // расширить за пределы centerRightPosition R,

        // настраиваем centerPosition C на основе расширенного палиндрома

        if (i + P[i] > R) 

        {

            C = i;

            R = i + P[i];

        }

    }

    return false;

}

  
// Код драйвера

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

}

  
// Этот код предоставлен PrinciRaj1992

C #

// C # реализация подхода

using System;

using System.Collections.Generic; 

  

class GFG 

{

  
// Функция для проверки, если мы нашли
// палиндром той же длины, что и вход
// который является вращением входной строки

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;

}

  
// Функция для предварительной обработки строки
// для алгоритма Манахера

static String reform(String s)

{

    String s1 = "$#";

  

    // Добавляем # между символами

    for (int i = 0; i < s.Length; i++) 

    {

        s1 += s[i];

        s1 += '#';

    }

  

    s1 += '@';

    return s1;

}

  
// Функция для поиска самого длинного палиндрома
// подстрока с использованием алгоритма Манахера

static bool longestPal(String s, int len) 

{

  

    // Текущая левая позиция

    int mirror = 0;

  

    // Правая позиция по центру

    int R = 0;

  

    // Центральная позиция

    int C = 0;

  

    // LPS Length Array

    int[] P = new int[s.Length];

    int x = 0;

  

    // Получить currentLeftPosition Mirror

    // для currentRightPosition i

    for (int i = 1; i < s.Length - 1; i++)

    {

        mirror = 2 * C - i;

  

        // Если currentRightPosition i

        // в пределах centerRightPosition R

        if (i < R) 

        {

            P[i] = Math.Min((R - i), P[mirror]);

        }

  

        // Попытка расширить палиндром по центру

        // at currentRightPosition i

        while (s[i + (1 + P[i])] == s[i - (1 + P[i])])

        {

            P[i]++;

        }

  

        // Проверка на палиндром

        bool ans = checkPal(P[i], len);

        if (ans) 

        {

            return true;

        }

  

        // Если палиндром центрирован на currentRightPosition i

        // расширить за пределы centerRightPosition R,

        // настраиваем centerPosition C на основе расширенного палиндрома

        if (i + P[i] > R) 

        {

            C = i;

            R = i + P[i];

        }

    }

    return false;

}

  
// Код драйвера

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

}

  
// Этот код предоставлен Rajput-Ji

Выход:

1

Эта статья предоставлена Абхай Рати . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Проверьте, является ли данная строка вращением палиндрома

0.00 (0%) 0 votes