โปรแกรมแบบเรียกซ้ำสำหรับแทรกเครื่องหมายดอกจันระหว่างตัวอักษรซ้ำกันใน C++

ภาพรวม

เมื่อได้รับสตริง str1 เป็นอินพุต เป้าหมายคือการแทรกเครื่องหมาย '*' ระหว่างคู่ของตัวอักษรที่เหมือนกันในสตริงอินพุต และส่งคืนสตริงผลลัพธ์โดยใช้วิธีการเรียกซ้ำ (Recursive)

ตัวอย่าง: หากอินพุตคือ "wellness" ผลลัพธ์จะเป็น "wel*lnes*s"

ตัวอย่าง

อินพุต − str1 = "happiness"

เอาต์พุต − สตริงหลังเพิ่ม * : hap*pines*s

คำอธิบาย − การเพิ่ม * ระหว่างคู่ pp และ ss ให้สตริงผลลัพธ์คือ hap*pines*s

อินพุต − str1 = "swimmmmingggg pooool"

เอาต์พุต − สตริงหลังเพิ่ม * : swim*m*m*ming*g*g*g po*o*o*ol

คำอธิบาย − เพิ่ม * ระหว่างคู่ mm, gg และ oo ให้ผลลัพธ์ swim*m*m*ming*g*g*g po*o*o*ol

แนวทางการแก้ปัญหา

แบ่งสตริงออกเป็นสองส่วนย่อยที่จุดดัชนีปัจจุบัน หากตัวอักษรสุดท้ายของส่วนแรกตรงกับตัวอักษรแรกของส่วนที่สอง ให้รวมสตริงเดิมใหม่เป็น ส่วนแรก + '*' + ส่วนที่สอง หยุดการเรียกซ้ำเมื่อความยาวของส่วนที่สองเท่ากับ 0

• รับสตริงอินพุต str1 และคำนวณความยาว len
• ฟังก์ชัน addStar(string& s1, int i, int len1) รับสตริง ความยาว และดัชนีปัจจุบัน แล้วเพิ่ม * หากคู่ตัวอักษรเหมือนกัน
• สร้าง tmp1 เป็นส่วนย่อยของ s1 จากดัชนี 0 ถึง i
• สร้าง tmp2 เป็นส่วนย่อยของ s1 จากดัชนี i ถึง len1 + 1
• หากตัวอักษรสุดท้ายของ tmp1 และตัวแรกของ tmp2 เท่ากัน ให้ตั้ง s1 = tmp1 + '*' + tmp2
• เรียก addStar(s1, i+1, len1) สำหรับรอบถัดไป
• พิมพ์ str1 ภายใน main

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

#include <iostream> 
using namespace std; 

void addStar(string& s1, int i, int len1){ 
    string tmp1 = s1.substr(0, i); 
    string tmp2 = s1.substr(i, len1 + 1); 
    if (tmp2.length() == 0){ 
        return; 
    } 
    if (tmp1[i-1] == tmp2[0]){ 
        s1 = tmp1 + '*' + tmp2; 
    } 
    addStar(s1, i+1, len1); 
} 

int main(){ 
    string str1 = "aabbcccdddd"; 
    int len = str1.length(); 
    addStar(str1, 0, len-1); 
    cout << "String after adding * : " << str1 << endl; 
    return 0; 
}

ผลลัพธ์

String after adding * : a*ab*bc*c*cd*d*d*d