Для заданной строки проверьте, можно ли переставить символы данной строки для формирования палиндрома.
Например, символы «geeksogeeks» могут быть переставлены для формирования палиндрома «geeksoskeeg», но символы «geeksforgeeks» не могут быть переставлены для формирования палиндрома.
Набор символов может образовывать палиндром, если не более одного символа встречается нечетное количество раз, а все символы встречаются четное количество раз.
Простое решение состоит в том, чтобы запустить два цикла, внешний цикл выбирает все символы один за другим, внутренний цикл подсчитывает количество вхождений выбранного символа. Мы отслеживаем нечетные счета. Временная сложность этого решения составляет O (n 2 ).
Мы можем сделать это за O (n) время, используя массив count. Ниже приведены подробные шаги.
1) Создайте массив счетчиков с размером алфавита, который обычно равен 256. Инициализируйте все значения массива счетчиков как 0.
2) Пройдите заданную строку и количество приращений каждого символа.
3) Перейдите к массиву счетчиков, и если массив счетчиков имеет более одного нечетного значения, верните false. В противном случае верните истину.
Ниже приведена реализация вышеуказанного подхода.
C ++
#include<bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
bool canFormPalindrome(string str)
{
int count[NO_OF_CHARS] = {0};
for (int i = 0; str[i]; i++)
count[str[i]]++;
int odd = 0;
for (int i = 0; i < NO_OF_CHARS; i++)
{
if (count[i] & 1)
odd++;
if (odd > 1)
return false;
}
return true;
}
int main()
{
canFormPalindrome("geeksforgeeks")? cout << "Yes\n":
cout << "No\n";
canFormPalindrome("geeksogeeks")? cout << "Yes\n":
cout << "No\n";
return 0;
}
|
Джава
import java.io.*;
import java.util.*;
import java.math.*;
class GFG {
static int NO_OF_CHARS = 256;
static boolean canFormPalindrome(String str) {
int count[] = new int[NO_OF_CHARS];
Arrays.fill(count, 0);
for (int i = 0; i < str.length(); i++)
count[(int)(str.charAt(i))]++;
int odd = 0;
for (int i = 0; i < NO_OF_CHARS; i++)
{
if ((count[i] & 1) == 1)
odd++;
if (odd > 1)
return false;
}
return true;
}
public static void main(String args[])
{
if (canFormPalindrome("geeksforgeeks"))
System.out.println("Yes");
else
System.out.println("No");
if (canFormPalindrome("geeksogeeks"))
System.out.println("Yes");
else
System.out.println("No");
}
}
|
python3
NO_OF_CHARS = 256
def canFormPalindrome(st) :
count = [0] * (NO_OF_CHARS)
for i in range( 0, len(st)) :
count[ord(st[i])] = count[ord(st[i])] + 1
odd = 0
for i in range(0, NO_OF_CHARS ) :
if (count[i] & 1) :
odd = odd + 1
if (odd > 1) :
return False
return True
if(canFormPalindrome("geeksforgeeks")) :
print("Yes")
else :
print("No")
if(canFormPalindrome("geeksogeeks")) :
print("Yes")
else :
print("No")
|
C #
using System;
class GFG {
static int NO_OF_CHARS = 256;
static bool canFormPalindrome(string str) {
int[] count = new int[NO_OF_CHARS];
Array.Fill(count, 0);
for (int i = 0; i < str.Length; i++)
count[(int)(str[i])]++;
int odd = 0;
for (int i = 0; i < NO_OF_CHARS; i++)
{
if ((count[i] & 1) == 1)
odd++;
if (odd > 1)
return false;
}
return true;
}
public static void Main()
{
if (canFormPalindrome("geeksforgeeks"))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
if (canFormPalindrome("geeksogeeks"))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
|
Выход:
No
Yes
Эта статья предоставлена Abhishek. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Другой подход:
Мы можем сделать это за O (n) время, используя список. Ниже приведены подробные шаги.
1) Создайте список персонажей.
2) Пройдите заданную строку.
3) Для каждого символа в строке удалите символ, если список уже содержит, добавьте в список.
3) Если длина строки четная, то ожидается, что список будет пустым.
4) Или, если длина строки нечетная, размер списка должен быть 1
5) При указанных выше двух условиях (3) или (4) верните true, иначе верните false.
Джава
import java.util.ArrayList;
import java.util.List;
class GFG{
static boolean canFormPalindrome(String str) {
List<Character> list = new ArrayList<Character>();
for (int i = 0; i < str.length(); i++) {
if (list.contains(str.charAt(i)))
list.remove((Character) str.charAt(i));
else
list.add(str.charAt(i));
}
if (str.length() % 2 == 0 && list.isEmpty()
|| (str.length() % 2 == 1 && list.size() == 1))
return true;
else
return false;
}
public static void main(String args[]) {
if (canFormPalindrome("geeksforgeeks"))
System.out.println("Yes");
else
System.out.println("No");
if (canFormPalindrome("geeksogeeks"))
System.out.println("Yes");
else
System.out.println("No");
}
}
|
C #
using System;
using System.Collections.Generic;
class GFG
{
static Boolean canFormPalindrome(String str)
{
List<char> list = new List<char>();
for (int i = 0; i < str.Length; i++)
{
if (list.Contains(str[i]))
list.Remove((char) str[i]);
else
list.Add(str[i]);
}
if (str.Length % 2 == 0 && list.Count == 0 ||
(str.Length % 2 == 1 && list.Count == 1))
return true;
else
return false;
}
public static void Main(String []args)
{
if (canFormPalindrome("geeksforgeeks"))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
if (canFormPalindrome("geeksogeeks"))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
|
Выход:
No
Yes
Рекомендуемые посты:
- Проверьте, можно ли переставить строку, чтобы сформировать специальный палиндром
- Проверьте, образуют ли символы в строке палиндром в O (1) лишний пробел
- Проверьте, можно ли переставить строку так, чтобы каждая подстрока нечетной длины была палиндромом
- Найти количество подстрок, символы которых можно переставить для формирования заданного слова
- Проверьте, можно ли поменять символы одной строки для формирования другой
- Минимальная длина подстроки, символы которой могут быть использованы для формирования палиндрома длиной K
- Перестановка символов для формирования палиндрома, если это возможно
- Минимальные перемещения для формирования строки путем добавления символов или добавления самой строки
- Проверьте, является ли двусвязный список символов палиндромом или нет
- Найдите игрока, который переставляет персонажей, чтобы сначала получить палиндромную строку
- Минимальное количество символов, добавляемых спереди, чтобы сделать строку палиндромом
- Минимальное количество символов, которое нужно заменить, чтобы составить заданную строку Палиндром
- Проверьте, возможно ли создать палиндромную строку из заданного N
- Проверьте, является ли данная строка вращением палиндрома
- Проверьте, является ли строка палиндромом в C, используя указатели
Проверьте, можно ли переставить символы данной строки, чтобы сформировать палиндром
0.00 (0%) 0 votes