По заданной строке проверьте, является ли она вращением палиндрома. Например, ваша функция должна возвращать 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;
bool isPalindrome(string 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)
{
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;
}
|
Джава
import java.io.*;
class Palindrome {
static boolean isPalindrome(String 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)
{
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);
}
}
|
питон
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"
|
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)
{
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);
}
}
|
Выход:
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 ++
#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;
int P[s.size()] = { 0 };
int x = 0;
for (int i = 1; i < s.size() - 1; i++) {
mirror = 2 * C - i;
if (i < R)
P[i] = min((R - i), P[mirror]);
while (s[i + (1 + P[i])] == s[i - (1 + P[i])]) {
P[i]++;
}
bool ans = checkPal(P[i], len);
if (ans)
return true;
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;
}
|
Джава
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;
int[] P = new int[s.length()];
int x = 0;
for (int i = 1; i < s.length() - 1; i++)
{
mirror = 2 * C - i;
if (i < R)
{
P[i] = Math.min((R - i), P[mirror]);
}
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;
}
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);
}
}
|
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;
int[] P = new int[s.Length];
int x = 0;
for (int i = 1; i < s.Length - 1; i++)
{
mirror = 2 * C - i;
if (i < R)
{
P[i] = Math.Min((R - i), P[mirror]);
}
while (s[i + (1 + P[i])] == s[i - (1 + P[i])])
{
P[i]++;
}
bool ans = checkPal(P[i], len);
if (ans)
{
return true;
}
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);
}
}
|
Выход:
1
Эта статья предоставлена Абхай Рати . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Рекомендуемые посты:
- Программа на C, чтобы проверить, является ли данная строка палиндромом
- Проверьте, является ли данная строка палиндромом, используя стек
- Проверьте, является ли какая-либо анаграмма строки палиндромом или нет
- Проверьте, является ли строка палиндромом в C, используя указатели
- Проверьте, возможно ли создать палиндромную строку из заданного N
- Левое вращение и правое вращение струны
- Рекурсивная функция для проверки, является ли строка палиндромом
- Учитывая две строки, проверьте, какая строка делает палиндром первым
- Python программа для проверки, является ли строка палиндромом или нет
- Java-программа для проверки, является ли строка палиндромом
- Проверьте, существует ли какая-либо подпоследовательность в строке, которая не является палиндромом
- Проверьте, можно ли переставить символы данной строки, чтобы сформировать палиндром
- Проверьте, можно ли переставить строку, чтобы сформировать специальный палиндром
- Программа Python для проверки, является ли данная строка гласной Палиндром
- Программа клиент-сервер TCP для проверки, является ли данная строка палиндромной
Проверьте, является ли данная строка вращением палиндрома
0.00 (0%) 0 votes