พิมพ์ตำแหน่งที่จัดเรียงของอักขระเพื่อสร้าง palindrome ในโปรแกรม C

คุณจะได้รับสตริง str ที่มีความยาว n พิมพ์ตำแหน่งของทุกองค์ประกอบของสตริงเพื่อสร้าง palindrome หรือพิมพ์ข้อความ "No palindrome" บนหน้าจอ

พาลินโดรมคืออะไร

Palindrome คือคำ ลำดับตัวอักษรที่อ่านจากข้างหลังหรือข้างหลังเหมือนกันว่าอ่านจากข้างหน้า เช่น MADAM รถแข่ง

ในการค้นหาลำดับหรือคำคือ palindrome เรามักจะเก็บส่วนกลับของคำในสตริงที่แยกจากกัน และเปรียบเทียบทั้งสองอย่างหากเหมือนกันแล้ว คำหรือลำดับที่กำหนดคือ palindrome แต่ในคำถามนี้เราต้องพิมพ์การจัดเรียงเพื่อสร้างคำหรือลำดับใน palindrome

เช่น มีสตริง str =“tinni” ซึ่งสามารถเป็น intni หรือ nitin ได้ ดังนั้นเราต้องคืนค่าลำดับการจัดเรียงตัวใดตัวหนึ่งเป็นดัชนีเริ่มต้นจาก 1 และผลลัพธ์อาจเป็น 2 3 1 4 5 หรือ 3 2 1 5 4 จากทั้งสอง

ปัญหาข้างต้นต้องการวิธีแก้ไขดังตัวอย่างด้านล่าง −

ตัวอย่าง

Input: string str = “baa”
Output: 2 1 3
Input: string str = “tinni”
Output: 2 3 1 4 5

อัลกอริทึม

void printPalindromePos(string &str)
START
STEP 1: DECLARE vector<int> pos[MAX]
STEP 2: DECLARE AND ASSIGN n WITH LENGTH OF str
STEP 3: LOOP FOR i = 0 AND i < n AND i++
   pos[str[i]].push_back(i+1)
END LOOP
STEP 4: SET oddCount = 0
STEP 5: DECLARE oddChar
STEP 6: LOOP FOR i=0 AND i<MAX AND i++
   IF pos[i].size() % 2 != 0 THEN,
      INCREMENT oddCount BY 1
      SET oddChar AS i
   END IF
END FOR
STEP 7: IF oddCount > 1 THEN,
   PRINT "NO PALINDROME"
STEP 8: LOOP FOR i=0 AND i<MAX AND i++
   DECRLARE mid = pos[i].size()/2
   LOOP FOR j=0 AND j<mid AND j++
      PRINT pos[i][j]
   END LOOP
END LOOP
STEP 9: IF oddCount > 0 THEN,
   DECLARE AND SET last = pos[oddChar].size() - 1
   PRINT pos[oddChar][last]
   SET pos[oddChar].pop_back();
END IF
STEP 10: LOOP FOR i=MAX-1 AND i>=0 AND i--
   DECLARE AND SET count = pos[i].size()
   LOOP FOR j=count/2 AND j<count AND j++
      PRINT pos[i][j]
STOP

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
// Giving the maximum characters
const int MAX = 256;
void printPalindromePos(string &str){
   //Inserting all positions of characters in the given string.
   vector<int> pos[MAX];
   int n = str.length();
   for (int i = 0; i < n; i++)
      pos[str[i]].push_back(i+1);
      /* find the number of odd elements.Takes O(n) */
   int oddCount = 0;
   char oddChar;
   for (int i=0; i<MAX; i++) {
      if (pos[i].size() % 2 != 0) {
         oddCount++;
         oddChar = i;
      }
   }
   /* Palindrome can't contain more than 1 odd characters */
   if (oddCount > 1)
      cout << "NO PALINDROME";
   /* Print positions in first half of palindrome */
   for (int i=0; i<MAX; i++){
      int mid = pos[i].size()/2;
      for (int j=0; j<mid; j++)
         cout << pos[i][j] << " ";
   }
   // Consider one instance odd character
   if (oddCount > 0){
      int last = pos[oddChar].size() - 1;
      cout << pos[oddChar][last] << " ";
      pos[oddChar].pop_back();
   }
   /* Print positions in second half of palindrome */
   for (int i=MAX-1; i>=0; i--){
      int count = pos[i].size();
      for (int j=count/2; j<count; j++)
      cout << pos[i][j] << " ";
   }
}
int main(){
   string s = "tinni";
   printPalindromePos(s);
   return 0;
}

ผลลัพธ์

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

2 3 1 4 5