連続する母音を削除して修正後のテキストを求めるC++コード

文字列 S(n 文字)が与えられていると仮定します。あるテキストエディタには奇妙なルールがあり、その校正機能は次のように動作します。単語の中に母音が 2 つ連続して現れる限り、先頭側の母音を 1 つずつ削除していきます。連続する母音がなくなった時点で、その単語は「正しい」と判断されます。ここで母音として扱うのは、「a」「e」「i」「o」「u」「y」の 6 文字です。私たちの目的は、文字列 S にこの校正処理を適用した結果、つまり修正後の単語を求めることです。

例えば、入力が S = "poor" の場合、「o」が 2 つ連続しているため最初の「o」が削除され、出力は「por」になります。

解法のアプローチ

この問題は、文字列を先頭から順に走査しながら、隣接する 2 文字がどちらも母音かどうかをチェックすることで解けます。両方が母音であれば、現在位置の文字を削除し、インデックスを 1 つ戻して同じ位置を再確認します。これにより、「ooo」のような 3 文字以上連続する母音にも正しく対応できます。

アルゴリズムの手順

1. S の長さを n とし、母音の集合 t = "aeiouy" を用意します。
2. i を 1 から初期化し、i < n の間、i を 1 ずつ増やしながら繰り返します。
3. S[i] が t に含まれ、かつ S[i - 1] も t に含まれる場合は、S の i 番目の文字を削除し、i を 1 減らします。
4. ループ終了後、修正済みの S を返します。

C++ 実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
    int n = S.size();
    string t = "aeiouy";
    for (int i = 1; i < n; i++){
        if (t.find(S[i]) != -1 && t.find(S[i - 1]) != -1){
            S.erase(i, 1);
            i--;
        }
    }
    return S;
}
int main(){
    string S = "poor";
    cout << solve(S) << endl;
}

ポイント解説

• i-- を行う理由: 文字を削除すると後続の文字が左に詰められるため、インデックスを 1 つ戻して同じ位置を再チェックしないと、連続する 3 文字以上の母音を見逃してしまう可能性があります。
• y も母音として扱う: 通常は子音とされることが多い y ですが、この問題では母音の一部として処理します。
• 計算量について: 文字列の走査は O(n) ですが、erase 操作には文字のシフトが伴うため、母音が大量に連続するような最悪ケースでは O(n²) となります。

入力

"poor"

出力

por