จัดเรียงอักขระใหม่เพื่อสร้าง palindrome ถ้าเป็นไปได้ใน C++

เราได้รับสตริง 'str' ที่มีความยาวเท่าใดก็ได้ งานคือการจัดเรียงอักขระใหม่ในลักษณะที่ผลลัพธ์จะเป็นสตริง palindrome โดยไม่ต้องเพิ่มหรือลบอักขระออกจากสตริงอินพุตที่กำหนด สตริง Palindrome เป็นสตริงที่อักขระถูกจัดเรียงในลักษณะที่ออกเสียงเหมือนกันตั้งแต่ต้นและสุดท้าย

ให้เราดูสถานการณ์อินพุตเอาต์พุตที่หลากหลายสำหรับสิ่งนี้ -

ป้อนข้อมูล − string str ="อิทนิน"

ผลผลิต − การจัดเรียงอักขระใหม่เพื่อสร้าง palindrome ถ้าเป็นไปได้คือ:nitin

คำอธิบาย − เราได้รับตัวแปรประเภทสตริง สมมติว่า str ตอนนี้ เราจะจัดเรียงอักขระของสตริงอินพุตใหม่ในลักษณะที่จะเป็นสตริงพาลินโดรม และหากเป็นไปไม่ได้ อักขระดังกล่าวจะส่งคืน 'ไม่เป็นไปได้' ดังนั้นเอาต์พุตที่มีสตริงอินพุตที่กำหนดคือ 'nitin'

ป้อนข้อมูล − string str ="baaaba"

ผลผลิต − การจัดเรียงอักขระใหม่ให้กลายเป็น palindrome ถ้าเป็นไปได้คือ:aabbaa

คำอธิบาย − เราได้รับตัวแปรประเภทสตริง สมมติว่า str ตอนนี้ เราจะจัดเรียงอักขระของสตริงอินพุตใหม่ในลักษณะที่จะเป็นสตริงพาลินโดรม และหากไม่สามารถทำได้ อักขระนั้นจะส่งกลับ "เป็นไปไม่ได้" ดังนั้นเอาต์พุตที่มีสตริงอินพุตที่กำหนดคือ 'aabbaa'

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ป้อนตัวแปรประเภทสตริง สมมติว่า str และคำนวณขนาดของสตริงและเก็บไว้ในความยาวที่ตั้งชื่อตัวแปร

• ส่งข้อมูลไปยังฟังก์ชัน Rearrangement(str, length)

• ภายในฟังก์ชัน การจัดเรียงใหม่ (arr, length)

  • สร้างตัวแปรเป็น 'um' ของประเภท unordered_map ที่จัดเก็บคู่ของประเภทถ่านและจำนวนเต็ม

  • ประกาศตัวแปรประเภทจำนวนเต็มเป็นผลรวมและตั้งค่าเป็น 0

  • สร้างตัวแปรประเภทอักขระเป็น 'ch' และตัวแปรประเภทสตริงเป็น str_1 และ str_2

  • เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง i น้อยกว่าความยาว ภายในลูป ตั้งค่า um[str[i]] ด้วยค่าที่เพิ่มขึ้นเป็น 1

  • เริ่มวนซ้ำ FOR เพื่อวนซ้ำแผนที่ 'อืม' ภายในลูป ให้ตรวจสอบว่า it.second % 2 ไม่เท่ากับ 0 แล้วเพิ่มผลรวม 1 และตั้งค่า ch ด้วย it.first

  • ตรวจสอบว่าผลรวมมากกว่า 1 หรือผลรวม =1 AND ความยาว % 2 =0 แล้วคืนค่า 0

  • เริ่มวนซ้ำ FOR เพื่อวนซ้ำแผนที่ 'อืม' ภายในลูป ให้ตั้งค่า str(it.second / 2, it.first), str_1 เป็น str_1 + str และ str_2 เป็น str + str_2

  • ตรวจสอบ IF total =1 แล้วคืนค่า str_1 + ch + str_2 ELSE ให้คืนค่า str_1 + str_2

• พิมพ์ผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
string Rearrangement(string str, int length){
   unordered_map<char, int> um;
   int total = 0;
   char ch;
   string str_1 = "";
   string str_2 = "";

   for (int i = 0; i < length; i++){
      um[str[i]]++;
   }
   for(auto it : um){
      if(it.second % 2 != 0){
         total++;
         ch = it.first;
      }
   }
   if(total > 1 || total == 1 && length % 2 == 0){
      return 0;
   }
   for(auto it : um){
      string str(it.second / 2, it.first);
      str_1 = str_1 + str;
      str_2 = str + str_2;
   }
   if(total == 1){
      return str_1 + ch + str_2;
   }
   else{
      return str_1 + str_2;
   }
}
int main(){
   string str = "itnin";
   int length = str.size();
   cout<<"Rearrangement of characters to form palindrome if possible is: "<<Rearrangement(str, length);
   return 0;
}

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

Rearrangement of characters to form palindrome if possible is: nitin