【C++】同じ文字のペアの間に「*」を挿入する再帰プログラムの実装方法

文字列 str1 が入力として与えられます。この記事のゴールは、入力文字列内で同一の文字が隣り合うペアの間に「*」を挿入し、再帰的なアプローチを用いて結果の文字列を返すことです。

たとえば、入力文字列が str1 = "wellness" の場合、出力は "wel*lne*s*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 が得られます。

プログラムで使用しているアプローチ

このアプローチでは、まず文字列 str1 を受け取ります。各反復処理において、現在のインデックスを境界として str1 を前半と後半の2つの部分文字列に分割します。前半の部分文字列の末尾の文字と、後半の部分文字列の先頭の文字が一致した場合は、元の文字列を「部分文字列1 + '*' + 部分文字列2」に更新します。そして、後半の部分文字列の長さが 0 になった時点で再帰を終了します。

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

• 関数 addStar(string& s1, int i, int len1) は、文字列 s1 とその長さ、現在のインデックスを引数として受け取り、隣り合う2文字が同じ場合に * を挿入します。

• tmp1 として、s1 のインデックス 0 から i までの部分文字列を取得します。

• tmp2 として、s1 のインデックス i から len1 + 1 までの部分文字列を取得します。

• tmp1 の末尾の文字と tmp2 の先頭の文字が等しい場合、s1 = tmp1 + '*' + tmp2 に更新します。

• 次の反復のために addStar(s1, i+1, len1); を呼び出します。

• 最後に main 関数内で 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