C++で同一の文字のペアの間にスターを挿入する再帰プログラム

入力として文字列str1を指定します。目標は、入力文字列内の同一の文字のペアの間に「*」を挿入し、再帰的アプローチを使用して結果の文字列を返すことです。

入力文字列がstr1= "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のペアの間に*を追加すると、結果の文字列 smile * m * m * ming * g * g * g po * o * o * olが得られます。

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、文字列str1を使用します。各反復で、現在のインデックスを中間点としてstr1を2つに分割します。最初のサブストリングの最後の文字が次のサブストリングの最初の文字と同じである場合は、元のストリングをサブストリング1、「*」、サブストリング2の順に設定します。 substring2の長さが0の場合、再帰を終了します。

• 入力文字列をstr1とし、その長さをlenとして計算します。

• 関数addStar（string＆s1、int i、int len1）は、s1の長さと現在のインデックスを入力として受け取り、2組の文字が同じ場合は*を追加します。

• tmp1をインデックス0からiまでのs1のサブストリングとして取得します

• tmp2をインデックスiからlen1+1までのs1のサブストリングとして取得します。

• tmp1の最後の文字とtmp2の最初の文字が等しい場合は、s1 =tmp1 +’*’+tmp2を設定します。

• addStar（s1、i + 1、len1）;を呼び出します。次の反復のために。

• 最後に、メイン内のstr1を印刷します。

例

#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