【C++】i番目の文字が元の単語の(i-1)番目・i番目・(i+1)番目のいずれかである単語の個数を求める

文字列 str[] が入力として与えられます。この問題の目的は、str[] と同じ長さを持ち、i番目の文字が元の単語の (i-1)番目・i番目・(i+1)番目のいずれかの文字で置き換えられた単語の個数を数えることです。

なお、先頭の文字は「i番目 または (i+1)番目」の文字から、末尾の文字は「(i-1)番目 または i番目」の文字から選ぶことになります。

具体例を使って理解していきましょう。

入力 − str[] = "TPP"

出力 − i番目の文字が元の単語の(i-1)番目・i番目・(i+1)番目のいずれかである単語の個数：4

説明

T を T（i番目）または 1つ目の P（i+1番目）で置き換える → TPP, PPP
1つ目の P を T（i-1番目）、P（i番目）、P（i+1番目）で置き換える → TTP, TPP, TPP
2つ目の P を P（i-1番目）または P（i番目）で置き換える → TPP, TPP
置き換えのユニークな組み合わせ：TPP, PPP, TTP, PTP

入力 − str[] = "aaa"

出力 − i番目の文字が元の単語の(i-1)番目・i番目・(i+1)番目のいずれかである単語の個数：1

説明

a を a（i番目）または 2つ目の a（i+1番目）で置き換える → aaa, aaa
2つ目の a を a（i-1番目）、a（i番目）、a（i+1番目）で置き換える → aaa, aaa, aaa
3つ目の a を a（i-1番目）または a（i番目）で置き換える → aaa, aaa
置き換えのユニークな組み合わせ：aaa

プログラムで使用するアプローチ

各文字には最大で3通りの候補があります。現在注目している文字 i に対して、(i-1)番目・i番目・(i+1)番目の3文字がすべて異なれば選択肢は3つ、そのうち2つが同じなら2つ、3つとも同じなら1つです。

そこで、文字列を先頭から走査しながら文字の重複を判定し、その結果に応じてカウントに 3・2・1 を掛けていきます。先頭と末尾の文字については候補が2つしかないため、同様に重複を判定して 2 または 1 を掛けます。

• 文字列 str[] を文字配列として受け取る。
• 関数 total(char str[], int length) が文字列を受け取り、条件を満たす単語の個数を返す。
• 初期カウントを 1 とする（str[] 自身も条件を満たす単語のひとつであるため）。
• 文字列の長さが 1 の場合は 1 を返す。
• 先頭の文字（インデックス 0）をチェックし、str[0] == str[1] ならカウントを 1 倍、異なれば 2 倍する。
• for ループでインデックス i=1 から i<length-1 まで走査する。
• 各位置 i において、str[i]、str[i-1]、str[i+1] の3文字を比較する。
• 3文字すべてが同じならカウントを 1 倍、任意の2つが同じなら 2 倍、すべて異なれば 3 倍する。
• 末尾の文字については、str[length-1] == str[length-2] ならカウントを 1 倍、異なれば 2 倍する。
• 走査が終わった時点で、カウントには条件を満たす相異なる単語の個数が格納されている。
• カウントを結果として返す。

この手法では文字列を一度だけ走査すればよいため、時間計算量は O(n)、追加のメモリ使用量は O(1) で済む点も大きなメリットです。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
int total(char str[], int length){
   int count = 1;
   if (length == 1){
      return count;
   }
   if (str[0] == str[1]){
      count = count * 1;
   }
   else{
      count = count * 2;
   }
   for (int j=1; j<length-1; j++){
      if (str[j] == str[j-1] && str[j] == str[j+1]){
         count = count * 1;
      }
      else if (str[j] == str[j-1]){
         count = count * 2;
      }
      else if(str[j] == str[j+1]){
         count = count * 2;
      }
      else if(str[j-1] == str[j+1]){
         count = count * 2;
      }
      else{
         count = count * 3;
      }
   }
   if (str[length - 1] == str[length - 2]){
      count = count * 1;
   }
   else{
      count = count * 2;
   }
   return count;
}
int main(){
   char str[] = "TPP";
   int length = strlen(str);
   cout<<"i番目の文字が元の単語の(i-1)番目・i番目・(i+1)番目のいずれかである単語の個数："<<total(str, length) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます −

i番目の文字が元の単語の(i-1)番目・i番目・(i+1)番目のいずれかである単語の個数：4