ការអនុញ្ញាត Palindrome


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ Facebook ក្រុមហ៊ុន Microsoft
ហាស់ ហាសហាស។ ខ្សែអក្សរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា "ការអនុញ្ញាត Palindrome" បញ្ជាក់ថាអ្នកត្រូវបានផ្តល់ឱ្យ ខ្សែអក្សរ។ ពិនិត្យមើលថាតើវាអាចត្រូវបានរៀបចំឡើងវិញដើម្បីបង្កើតខ្សែអក្សរក្រេឌីណាមិច។

ឧទាហរណ៍

superdupers
yes

ការពន្យល់

ខ្សែបញ្ចូលដែលបានផ្តល់អាចត្រូវបានរៀបចំឡើងវិញ superdrepus។ វាគឺជាខ្សែរក្រអូមមាត់។ ដូច្នេះចម្លើយរបស់យើងចំពោះឧទាហរណ៍នេះគឺត្រូវហើយ។

វិធីសាស្រ្ត

ប្រសិនបើតួអក្សរទាំងអស់កើតឡើងសូម្បីតែចំនួនដងហើយភាគច្រើនតួអក្សរមួយកើតឡើងចំនួនសេសនៃដងបន្ទាប់មកខ្សែអក្សរអាចត្រូវបានបម្លែងទៅជាខ្សែអក្សរ palindromic ។

ដើម្បីអនុវត្តវិធីសាស្រ្តនេះយើងរក្សាអារេរាប់ទំហំ ១២៨ និងចាប់ផ្តើមជាមួយសូន្យ។ បំបែកតាមរយៈខ្សែអក្សរនិងបង្កើនចំនួនតួអក្សរនីមួយៗដែលបានជួបប្រទះនៅក្នុងអារេមួយ។ ឥឡូវត្រូវឆ្លងកាត់អារេហើយប្រសិនបើមានតួអក្សរច្រើនកើតឡើងចំនួនសេសបន្ទាប់មកត្រលប់មកវិញមិនពិត។

ការអនុញ្ញាត Palindrome

លេខកូដ

កូដ C ++ សម្រាប់ការអនុញ្ញាត Palindrome

// 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

កូដចាវ៉ាសំរាប់ការអនុញ្ញាត Palindrome

// 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

ការវិភាគស្មុគស្មាញ

ភាពស្មុគស្មាញពេលវេលា

អូរ (n) ដោយសារតែយើងកំពុងឆ្លងកាត់អារេតែម្តងដើម្បីពិនិត្យមើលថាតើខ្សែអក្សរដែលបានផ្តល់ឱ្យអាចត្រូវបានបម្លែងទៅជាខ្សែអក្សរ palindromic មួយ។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាក្លាយជា O (n) ។

ភាពស្មុគស្មាញនៃលំហ

ភាពស្មុគស្មាញនៃចន្លោះសម្រាប់កម្មវិធីដើម្បីពិនិត្យមើលថាតើខ្សែអក្សរដែលបានផ្តល់ឱ្យអាចត្រូវបានបម្លែងទៅជាខ្សែអក្សរ palindromic ឱ (១) ពីព្រោះយើងកំពុងប្រើអារេទំហំ ១២៨ ដើម្បីទុកប្រេកង់នៃតួអក្សរនីមួយៗ។

វិធីសាស្ត្រមានប្រសិទ្ធភាព

នៅក្នុងវិធីសាស្រ្តនេះយើងនឹងរក្សាបញ្ជី។ បន្ទាប់មកយើងនឹងធ្វើឱ្យប្រសើរឡើងតាមរយៈខ្សែអក្សរហើយប្រសិនបើតួអក្សរមានរួចហើយនៅក្នុងបញ្ជីយើងដកវាចេញផ្សេងទៀតយើងបញ្ចូលតួអក្សរនោះទៅក្នុងបញ្ជី។ បន្ទាប់ពីការនិយាយឡើងវិញប្រសិនបើចំនួនធាតុនៅក្នុងបញ្ជីគឺធំជាងមួយ។ ដូច្នេះវាមិនអាចត្រូវបានបំលែងទៅជាខ្សែអក្សរដែលមានពន្លឺព្រះអាទិត្យទេ។

លេខកូដ

លេខកូដ C ++ ល្អប្រសើរសម្រាប់ការអនុញ្ញាត Palindrome

#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

លេខកូដជ្វាប្រសើរសម្រាប់ការអនុញ្ញាត 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

ការវិភាគស្មុគស្មាញ

ភាពស្មុគស្មាញពេលវេលា

អូរ (n) ដោយសារតែយើងកំពុងឆ្លងកាត់អារេតែម្តងដើម្បីពិនិត្យមើលថាតើខ្សែអក្សរដែលបានផ្តល់ឱ្យអាចត្រូវបានបម្លែងទៅជាខ្សែអក្សរ palindromic មួយ។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាក្លាយជា O (n) ។

ភាពស្មុគស្មាញនៃលំហ

ភាពស្មុគស្មាញនៃចន្លោះសម្រាប់កម្មវិធីដើម្បីពិនិត្យមើលថាតើខ្សែអក្សរដែលបានផ្តល់ឱ្យអាចត្រូវបានបម្លែងទៅជាខ្សែសង្វាក់ក្រអូមមាត់គឺអូ (1) ។