Computer >> Máy Tính >  >> Lập trình >> C ++

Sắp xếp lại các ký tự để tạo thành palindrome nếu có thể trong C ++

Chúng tôi được cung cấp với một chuỗi ‘str’ có độ dài bất kỳ. Nhiệm vụ là sắp xếp lại các ký tự theo cách mà đầu ra sẽ là một chuỗi palindrome mà không cần thêm hoặc bớt một ký tự khỏi chuỗi đầu vào đã cho. Chuỗi Palindrome là chuỗi trong đó các ký tự được sắp xếp theo cách mà chúng phát âm giống nhau từ đầu đến cuối.

Hãy để chúng tôi xem các kịch bản đầu ra đầu vào khác nhau cho việc này -

Đầu vào - string str ="itnin"

Đầu ra - Sắp xếp lại các ký tự để tạo thành palindrome nếu có thể là:nitin

Giải thích - Chúng tôi được cung cấp một biến kiểu chuỗi, giả sử, str. Bây giờ chúng ta sẽ sắp xếp lại các ký tự của một chuỗi đầu vào theo cách mà nó sẽ là một chuỗi palindrome và nếu nó không thể giải quyết được thì nó sẽ trả về "NOT POSSIBLE". Vì vậy, đầu ra với chuỗi đầu vào đã cho là "nitin".

Đầu vào - string str ="baaaba"

Đầu ra - Sắp xếp lại các ký tự để tạo thành palindrome nếu có thể là:aabbaa

Giải thích - Chúng tôi được cung cấp một biến kiểu chuỗi, giả sử, str. Bây giờ chúng ta sẽ sắp xếp lại các ký tự của một chuỗi đầu vào theo cách mà nó sẽ là một chuỗi palindrome và nếu không thể thì nó sẽ trả về "NOT POSSIBLE". Vì vậy, đầu ra với chuỗi đầu vào đã cho là 'aabbaa'.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

  • Nhập một biến kiểu chuỗi, giả sử, str và tính toán kích thước của một chuỗi và lưu trữ nó trong một biến có độ dài được đặt tên.

  • Truyền dữ liệu vào hàm Sắp xếp lại (str, chiều dài).

  • Bên trong chức năng Sắp xếp lại (arr, length)

    • Tạo một biến dưới dạng "um" của kiểu unsrdered_map đang lưu trữ các cặp kiểu char và kiểu số nguyên.

    • Khai báo một biến kiểu số nguyên là tổng và đặt nó bằng 0.

    • Tạo một biến kiểu ký tự là ‘ch’ và các biến kiểu chuỗi là str_1 và str_2.

    • Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn độ dài. Bên trong vòng lặp, đặt um [str [i]] theo giá trị tăng dần là 1.

    • Bắt đầu vòng lặp FOR để lặp bản đồ ‘um’. Bên trong vòng lặp, hãy kiểm tra NẾU it. Giây% 2 không bằng 0, sau đó tăng tổng số lên 1 và đặt ch bằng nó. Đầu tiên.

    • Kiểm tra tổng số NẾU lớn hơn 1 HOẶC tổng số =1 VÀ độ dài% 2 =0 rồi trả về 0.

    • Bắt đầu vòng lặp FOR để lặp bản đồ ‘um’. Bên trong vòng lặp, đặt str (it.second / 2, it.first), str_1 thành str_1 + str và str_2 thành str + str_2.

    • Kiểm tra IF tổng =1 rồi trả về str_1 + ch + str_2. ELSE, trả về str_1 + str_2.

  • In kết quả.

Ví dụ 

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau 

Rearrangement of characters to form palindrome if possible is: nitin