Chương trình đệ quy để chèn một dấu sao giữa các cặp ký tự giống nhau trong C ++

Cho một chuỗi str1 làm đầu vào. Mục đích là chèn một dấu ‘*’ vào giữa một cặp ký tự giống nhau trong chuỗi đầu vào và trả về chuỗi kết quả bằng cách sử dụng phương pháp đệ quy.

Nếu chuỗi đầu vào là str1 = "wellness" thì đầu ra sẽ là "hàn * lnes * s"

Ví dụ

Đầu vào - str1 ="hạnh phúc"

Đầu ra - Chuỗi sau khi thêm *:hap * pines * s

Giải thích - Việc thêm * giữa các cặp pp và ss sẽ cho chúng ta chuỗi kết quả là hap * pines * s

Đầu vào - str1 =”bơimmmingggg pooool”

Đầu ra - Chuỗi sau khi thêm *:bơi * 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 sẽ cung cấp cho chúng tôi chuỗi kết quả bơi * m * m * ming * g * g * g po * o * o * ol

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Trong cách tiếp cận này lấy chuỗi str1. Trong mỗi lần lặp, chia str1 thành hai với chỉ mục hiện tại là điểm giữa. Nếu ký tự cuối cùng của chuỗi con đầu tiên giống với ký tự đầu tiên của chuỗi con tiếp theo thì hãy đặt chuỗi ban đầu là chuỗi con 1, theo sau là dấu ‘*’ theo sau là chuỗi con2. Kết thúc đệ quy trong trường hợp độ dài của chuỗi con2 bằng 0.

• Lấy chuỗi đầu vào là str1 và tính độ dài của nó dưới dạng len.

• Hàm addStar (string &s1, int i, int len1) lấy s1, độ dài và chỉ số hiện tại của nó làm đầu vào và thêm * nếu hai cặp ký tự giống nhau ..

• Lấy tmp1 làm chuỗi con của s1 từ chỉ mục 0 đến i

• Lấy tmp2 làm chuỗi con của s1 từ chỉ mục i đến len1 + 1.

• Nếu ký tự cuối cùng của tmp1 và ký tự đầu tiên của tmp2 bằng nhau thì hãy đặt s1 =tmp1 + ’*’ + tmp2.

• Gọi addStar (s1, i + 1, len1); cho lần lặp tiếp theo.

• Ở cuối, in str1 bên trong main.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

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