Cho một chuỗi str1 làm đầu vào. Mục tiêu là chèn ký tự '*' giữa mỗi cặp ký tự giống nhau liên tiếp trong chuỗi đầu vào và trả về chuỗi kết quả bằng phương pháp đệ quy.
Nếu chuỗi đầu vào là str1 = "wellness" thì đầu ra sẽ là "wel*lnes*s".
Ví dụ
Đầu vào - str1 = "happiness"
Đầu ra - Chuỗi sau khi thêm * : hap*pines*s
Giải thích - Thêm * giữa các cặp pp và ss cho chuỗi kết quả hap*pines*s.
Đầu vào - str1 = "swimmmmingggg pooool"
Đầu ra - Chuỗi sau khi thêm * : swim*m*m*ming*g*g*g po*o*o*ol
Giải thích - Thêm * giữa các cặp mm, gg và oo cho chuỗi kết quả swim*m*m*ming*g*g*g po*o*o*ol.
Phương pháp sử dụng trong chương trình dưới đây
Trong phương pháp này, lấy chuỗi str1. Ở mỗi lần lặp, tách str1 thành hai chuỗi con với chỉ số hiện tại làm điểm giữa. Nếu ký tự cuối của chuỗi con thứ nhất trùng với ký tự đầu của chuỗi con thứ hai, thì gán chuỗi gốc = chuỗi con 1 + '*' + chuỗi con 2. Kết thúc đệ quy khi độ dài chuỗi con 2 bằng 0.
Nhập chuỗi str1 và tính độ dài len.
Hàm addStar(string& s1, int i, int len1) nhận s1, độ dài và chỉ số hiện tại, thêm * nếu hai ký tự liên tiếp giống nhau.
Lấy tmp1 là chuỗi con của s1 từ chỉ số 0 đến i.
Lấy tmp2 là chuỗi con của s1 từ chỉ số i đến len1 + 1.
Nếu ký tự cuối của tmp1 và ký tự đầu của tmp2 bằng nhau thì gán s1 = tmp1 + '*' + tmp2.
Gọi addStar(s1, i+1, len1) cho lần lặp tiếp theo.
Cuối cùng in str1 trong main.
Ví dụ mã
#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 << "Chuỗi sau khi thêm * : "<<str1 << endl; return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Chuỗi sau khi thêm * : a*ab*bc*c*cd*d*d*d