隣接する文字がC++で1つ異なる文字列の数

入力としてnum番号が与えられます。目標は、隣接するすべての文字のASCII値の差が1になるように、長さnumの可能な文字列の数をカウントすることです。

numが2の場合、文字列は「ab」、「ba」、「bc」、「cb」、……..「yz」、「zy」になります。

例を挙げて理解しましょう

入力 − num =3

出力 −隣接する文字の違いが1である文字列の数は− 98

説明 −サンプル文字列には、「abc」、「aba」、「cde」…..「xyx」、「zyz」、「xyz」があります。

入力 − num =2

出力 −隣接する文字の違いが1である文字列の数は− 50

説明 −サンプル文字列には、「ab」、「ba」、「cd」…..「xy」、「zy」、「yz」があります。

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

長さ=2の場合。

a =“ ab”

b =“ ba”、“ bc”

c =“ cd”、“ cb”で始まる文字列...............

長さ=nの場合。

aで始まる文字列=bで始まる長さn-1の文字列の数の方法

bで始まる文字列=aまたはcで始まる長さn-1の文字列の数の方法

cで始まる文字列=bまたはdで始まる長さn-1の文字列の数の方法

動的計画法を使用してこれを解決します。

配列arr[num+1][27]を取ります。 arr[i][j]のアルファベット番号jで始まる長さiの文字列の数を含みます。文字列「a」、「b」...「z」の場合、すべてのarr[1][j]は1になります。

arr [2 to num + 1] [0 to 25]で休憩し、j=0の場合はarr[i][j] =arr [i-1] [j+1]に設定します。それ以外の場合は、arr [i] [j] =arr [i-1] [j-1] + arr [i-1] [j + 1];

結果は、num番目の行数の合計になります。

• 入力整数numを取得

• 関数difference_strings（int num）は、numを受け取り、隣接する文字の差が1である文字列の数を返します

• 初期カウントを0とします。

• arr [num +1][27]をすべて0で初期化します。

• arr [1] [0〜25]をすべて1で初期化します。

• 2D配列arr[][]をトラバースし、行2から最後まで2つのforループを使用し、26個のアルファベットすべてに対して列0から25を使用します。

• j =0の場合、開始文字は「a」です。現在のカウントをarr[i][j] =arr [i-1] [j + 1];

  として設定します

• それ以外の場合は、arr [i] [j] =（arr [i-1] [j-1] + arr [i-1] [j + 1]）

  を設定します。

• 上記のループが終了したら、最後の行をトラバースし、arr [num] [0〜25]を追加してカウントします。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int difference_strings(int num){
   long int count = 0;
   long int arr[num + 1][27];
   memset(arr, 0, sizeof(arr));
   for (int i = 0; i <= 25; i++){
      arr[1][i] = 1;
   }
   for (int i = 2; i <= num; i++){
      for (int j = 0; j <= 25; j++){
         if (j == 0){
            arr[i][j] = arr[i - 1][j + 1];
         }
         else{
            arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]);
         }
      }
   }
   for (int i = 0; i <= 25; i++){
      count = (count + arr[num][i]);
   }
   return count;
}
int main(){
   int num = 2;
   cout<<"Count of strings where adjacent characters are of difference one are: "<<difference_strings(num);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of strings where adjacent characters are of difference one are: 50