หาสตริงพาลินโดรม B ที่มี A เป็น subsequence ใน C++

โจทย์

ให้สตริง A ต้องการหาสตริง B ที่เป็นพาลินโดรม (อ่านจากหน้าหลังเท่ากัน) และ A เป็น subsequence ของ B (ได้จากการลบตัวอักษรบางตัวจาก B โดยไม่เปลี่ยนลำดับ)

ตัวอย่าง: A = "ab" → B = "abba" (พาลินโดรม และมี "ab" เป็น subsequence)

วิธีแก้ปัญหา

วิธีง่ายที่สุด: B = A + reverse(A) → ได้พาลินโดรมที่มี A เป็น subsequence อย่างแน่นอน

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
using namespace std;

bool isPalindrome(string str) {
    string temp = str;
    reverse(str.begin(), str.end());
    return str == temp;
}

string formPalindromeStr(string A) {
    string B = A;
    reverse(A.begin(), A.end());
    A = A + B;
    if (isPalindrome(B)) return B;
    return A;
}

string reverse(string input) {
    string temp = input;
    int left, right = 0;
    right = temp.length() - 1;
    for (left = 0; left < right; left++, right--)
        swap(temp[left], temp[right]);
    return temp;
}

int main(int argc, char const *argv[]) {
    string A = "Hello";
    cout << "The B is: " << formPalindromeStr(A);
}

ผลลัพธ์

The B is: olleHHello