Home  >  Article  >  Backend Development  >  Recursive program to insert an asterisk between a pair of identical characters in C++

Recursive program to insert an asterisk between a pair of identical characters in C++

WBOY
WBOYforward
2023-09-04 12:57:131410browse

Recursive program to insert an asterisk between a pair of identical characters in C++

Given a string str1 as input. The goal is to insert a "*" between a pair of identical characters in the input string and return the resulting string using a recursive method.

If the input string is str1 = "wellness", then the output will be "wel*lnes*s"

Example

Input - str1 = "happiness"

Output - The string after adding *: hap*pines*s

Explanation - Adding * between pp and ss will get the resulting string hap*pines*s

##Input - str1 = ”swimmmmingggg pooool”

Output - The string after adding *: swim*m*m*ming*g*g*g po*o*o*ol

Explanation - Adding * between mm, gg and oo will result in the string swim*m*m*ming*g*g*g po*o*o*ol

The method used in the following program is as follows

In this method, take the string str1. In each iteration, str1 is divided into two parts with the current index as the midpoint. If the last character of the first substring is the same as the first character of the next substring, then the original string is set to substring 1 followed by "*", followed by substring 2. If the length of substring 2 is 0, the recursion ends.

  • Take the input string as str1 and calculate its length as len.

  • The function addStar(string& s1, int i, int len1) accepts s1, its length and the current index as input, and adds * when the two pairs of characters are the same.

  • Take tmp1 as a substring from index 0 to i.

  • Take tmp2 as a substring from index i to len1 1.

  • If the last character of tmp1 is equal to the first character of tmp2, set s1=tmp1 ’*’ tmp2.

  • Call addStar(s1, i 1, len1) for the next iteration.

  • Finally print str1 in the main function.

Example

#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 + &#39;*&#39; + 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;
}

Output

If we run the above code it will generate the following output

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

The above is the detailed content of Recursive program to insert an asterisk between a pair of identical characters in C++. For more information, please follow other related articles on the PHP Chinese website!

Statement:
This article is reproduced at:tutorialspoint.com. If there is any infringement, please contact admin@php.cn delete