Перестановка паліндрому


Рівень складності Легко
Часто запитують у Facebook Microsoft
Мішанина Хешування рядок

Постановка проблеми

У проблемі “Перестановка паліндрому” зазначено, що вам дано a рядок. Перевірте, чи можна його переставити, щоб утворити паліндромну струну.

Приклад

superdupers
yes

Пояснення

Даний вхідний рядок можна переставити супердрепус. Це паліндромічна струна. Отже, наша відповідь на цей приклад - так.

Підхід

Якщо всі символи трапляються парною кількістю разів і щонайбільше один символ трапляється непарною кількістю разів, тоді рядок може бути перетворений у паліндромний рядок.

Для реалізації цього підходу ми підтримуємо масив лічильників розміром 128 і ініціалізуємо нулем. Перебирайте рядок і збільшуйте кількість кожного символу, що зустрічається в масиві. Тепер перебирайте масив, і якщо щонайменше один символ трапляється непарна кількість разів, тоді поверніть true, поверніть false.

Перестановка паліндрому

код

Код С ++ для перестановки паліндрому

// C++ implementation to check if 
// characters of a given string can 
// be rearranged to form a palindrome 
#include<bits/stdc++.h> 
using namespace std; 
#define NO_OF_CHARS 256 

/* function to check whether characters of a string can form 
a palindrome */
bool canFormPalindrome(string str) 
{ 
  // Create a count array and initialize all 
  // values as 0 
  int count[NO_OF_CHARS] = {0}; 

  // For each character in input strings, 
  // increment count in the corresponding 
  // count array 
  for (int i = 0; str[i]; i++) 
    count[str[i]]++; 

  // Count odd occurring characters 
  int odd = 0; 
  for (int i = 0; i < NO_OF_CHARS; i++) 
  { 
    if (count[i] & 1) 
      odd++; 

    if (odd > 1) 
      return false; 
  } 

  // Return true if odd count is 0 or 1, 
  return true; 
} 

/* Driver program*/
int main() 
{ 
canFormPalindrome("superdupers")? cout << "Yes\n": 
                  cout << "No\n"; 
return 0; 
}
Yes

Код Java для перестановки паліндрому

// Java implementation to check if 
// characters of a given string can 
// be rearranged to form a palindrome 
import java.io.*; 
import java.util.*; 
import java.math.*; 

class check { 

static int NO_OF_CHARS = 256; 

  /* function to check whether characters 
  of a string can form a palindrome */
  static boolean canFormPalindrome(String str) { 
  
  // Create a count array and initialize all 
  // values as 0 
  int count[] = new int[NO_OF_CHARS]; 
  Arrays.fill(count, 0); 

  // For each character in input strings, 
  // increment count in the corresponding 
  // count array 
  for (int i = 0; i < str.length(); i++) 
  count[(int)(str.charAt(i))]++; 

  // Count odd occurring characters 
  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 if odd count is 0 or 1, 
  return true; 
} 

// Driver program 
public static void main(String args[]) 
{ 
  if (canFormPalindrome("superdupers")) 
  System.out.println("Yes"); 
  else
  System.out.println("No"); 

} 
}
Yes

Аналіз складності

Часова складність

О (п) тому що ми об'їжджаємо масив лише один раз, щоб перевірити, чи може даний рядок бути перетворений у паліндромічний рядок. Тож складність часу стає O (n).

Космічна складність

Складність простору для програми, щоб перевірити, чи може даний рядок перетворитись на паліндромну, є O (1) оскільки ми використовуємо масив розміром 128 для зберігання частоти кожного символу.

Ефективний підхід

При такому підході ми будемо підтримувати список. Потім ми переглянемо рядок, і якщо символ вже присутній у списку, ми видаляємо його, інакше вставляємо цей символ у список. Після ітерації, якщо кількість елементів у списку більше одного. Отже, його неможливо перетворити на паліндромічний рядок.

код

Оптимізований код C ++ для перестановки паліндрому

#include<bits/stdc++.h> 
using namespace std; 

/* 
* function to check whether characters of 
a string can form a palindrome 
*/
bool canFormPalindrome(string str) 
{ 

  // Create a list 
  vector<char> list; 

  // For each character in input strings, 
  // remove character if list contains 
  // else add character to list 
  for (int i = 0; i < str.length(); i++) 
  { 
    auto pos = find(list.begin(), list.end(), str[i]); 
    if (pos != list.end()) 
    { 
      auto posi = find(list.begin(), list.end(),str[i]); 
      list.erase(posi); 
    } 
    else
      list.push_back(str[i]); 
  } 

  // if character length is even list is expected to be empty 
  // or if character length is odd list size is expected to be 1 
  if (str.length() % 2 == 0 && list.empty() // if string length is even 
    || (str.length() % 2 == 1 && list.size() == 1)) // if string length is odd 
    return true; 
  else
    return false; 

} 

// Driver program 
int main() 
{ 
  if (canFormPalindrome("superdupers")) 
    cout << ("Yes") << endl; 
  else
    cout << ("No") << endl; 
}
Yes

Оптимізований Java-код для перестановки Palindrome

import java.util.ArrayList; 
import java.util.List; 

class check{ 

  /* 
  * function to check whether characters of a string can form a palindrome 
  */
  static boolean canFormPalindrome(String str) { 

    // Create a list 
    List<Character> list = new ArrayList<Character>(); 

    // For each character in input strings, 
    // remove character if list contains 
    // else add character to list 
    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 character length is even list is expected to be empty 
    // or if character length is odd list size is expected to be 1 
    if (str.length() % 2 == 0 && list.isEmpty() // if string length is even 
        || (str.length() % 2 == 1 && list.size() == 1)) // if string length is odd 
      return true; 
    else
      return false; 

  } 

  // Driver program 
  public static void main(String args[]) { 
    if (canFormPalindrome("superdupers")) 
      System.out.println("Yes"); 
    else
      System.out.println("No"); 

  } 
}
Yes

Аналіз складності

Часова складність

О (п) тому що ми об'їжджаємо масив лише один раз, щоб перевірити, чи може даний рядок бути перетворений у паліндромічний рядок. Тож складність часу стає O (n).

Космічна складність

Складність простору для програми, щоб перевірити, чи може даний рядок перетворитись на паліндромну, є O (1).