Рубрики

Проверьте, можно ли переставить символы данной строки, чтобы сформировать палиндром

Для заданной строки проверьте, можно ли переставить символы данной строки для формирования палиндрома.
Например, символы «geeksogeeks» могут быть переставлены для формирования палиндрома «geeksoskeeg», но символы «geeksforgeeks» не могут быть переставлены для формирования палиндрома.

Набор символов может образовывать палиндром, если не более одного символа встречается нечетное количество раз, а все символы встречаются четное количество раз.

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

Мы можем сделать это за O (n) время, используя массив count. Ниже приведены подробные шаги.
1) Создайте массив счетчиков с размером алфавита, который обычно равен 256. Инициализируйте все значения массива счетчиков как 0.
2) Пройдите заданную строку и количество приращений каждого символа.
3) Перейдите к массиву счетчиков, и если массив счетчиков имеет более одного нечетного значения, верните false. В противном случае верните истину.

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

C ++

// реализация C ++ для проверки
// символы данной строки могут
// переставить для формирования палиндрома
#include<bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256

   
/ * функция, чтобы проверить, могут ли символы строки сформироваться

   палиндром * /

bool canFormPalindrome(string str)

{

    // Создаем массив count и инициализируем все

    // значения как 0

    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;

    }

   

    // Возвращаем true, если нечетное число равно 0 или 1,

    return true;

}

   
/ * Драйвер программы * /

int main()

{

  canFormPalindrome("geeksforgeeks")? cout << "Yes\n"

                                     cout << "No\n";

  canFormPalindrome("geeksogeeks")? cout << "Yes\n"

                                    cout << "No\n";

  return 0;

}

Джава

// реализация Java для проверки
// символы данной строки могут
// переставить для формирования палиндрома

import java.io.*;

import java.util.*;

import java.math.*;

  

class GFG {

  

static int NO_OF_CHARS = 256;

  

    / * функция для проверки наличия символов

    струны могут образовывать палиндром * /

    static boolean canFormPalindrome(String str) {

      

    // Создаем массив count и инициализируем все

    // значения как 0

    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;

    }

  

    // Возвращаем true, если нечетное число равно 0 или 1,

    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

# Реализация Python3 для проверки
# символов данной строки может
# переставить, чтобы сформировать палиндром

  

NO_OF_CHARS = 256

  
# функция для проверки наличия символов
# строки может образовывать палиндром

def canFormPalindrome(st) :

  

    # Создайте массив count и инициализируйте

    # все значения как 0

    count = [0] * (NO_OF_CHARS)

  

    # Для каждого символа во входных строках

    количество приращений в соответствующем

    # count array

    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

              

    # Вернуть true, если нечетное число равно 0 или 1,

    return True

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

if(canFormPalindrome("geeksforgeeks")) :

    print("Yes")

else :

    print("No")

      

if(canFormPalindrome("geeksogeeks")) :

    print("Yes")

else :

    print("No")

  
# Этот код предоставлен Никитой Тивари.

C #

// реализация C # для проверки
// символы данной строки могут
// переставить для формирования палиндрома

  

using System;

   

class GFG {

   

static int NO_OF_CHARS = 256;

   

    / * функция для проверки наличия символов

    струны могут образовывать палиндром * /

    static bool canFormPalindrome(string str) {

       

    // Создаем массив count и инициализируем все

    // значения как 0

    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;

    }

   

    // Возвращаем true, если нечетное число равно 0 или 1,

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

        }

  

        // если длина символа четная, список должен быть пустым

        // или если длина символа нечетная, размер списка ожидается равным 1

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

    }

}

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

C #

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

        }

  

        // если длина символа четная

        // список должен быть пустым

        // или если длина символа нечетная

        // размер списка ожидается равным 1

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

    }

}

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

Выход:

No
Yes

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

Проверьте, можно ли переставить символы данной строки, чтобы сформировать палиндром

0.00 (0%) 0 votes