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

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

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

พาลินโดรมคือคำหรือลำดับตัวอักษรที่อ่านจากหน้าหรือหลังได้เหมือนกัน เช่น MADAM, racecar

ปกติเราจะเก็บสตริงย้อนกลับในตัวแปรแยกและเปรียบเทียบ แต่โจทย์นี้ต้องการพิมพ์การจัดเรียงดัชนี (เริ่มจาก 1) ที่ทำให้เป็นพาลินโดรม

เช่น สตริง "tinni" สามารถจัดเป็น "intni" หรือ "nitin" ได้ ดัชนีที่เป็นไปได้คือ 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 pos[MAX]
STEP 2: DECLARE AND ASSIGN n WITH LENGTH OF str
STEP 3: LOOP FOR i = 0; i < n; 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; i 1 THEN
          PRINT "NO PALINDROME"
STEP 8: LOOP FOR i=0; i 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; i>=0; i--
          DECLARE AND SET count = pos[i].size()
          LOOP FOR j=count/2; j
ตัวอย่างโค้ด C++
#include 
using namespace std;
const int MAX = 256;
void printPalindromePos(string &str){
    vector pos[MAX];
    int n = str.length();
    for (int i = 0; i < n; i++)
        pos[str[i]].push_back(i+1);
    int oddCount = 0;
    char oddChar;
    for (int i=0; i 1)
        cout << "NO PALINDROME";
    for (int i=0; i 0){
        int last = pos[oddChar].size() - 1;
        cout << pos[oddChar][last] << " ";
        pos[oddChar].pop_back();
    }
    for (int i=MAX-1; i>=0; i--){
        int count = pos[i].size();
        for (int j=count/2; j
ผลลัพธ์
การรันโปรแกรมจะได้ผลลัพธ์ดังนี้:
2 3 1 4 5