C++で母音と子音を交互に配置した文字列を生成する方法

与えられた文字列に対して、母音と子音が交互に現れるように文字を並べ替えることを考えます。適切に並べ替えられない場合は「no such string」と表示してください。また、母音同士・子音同士の相対的な順序は元の文字列のまま維持する必要があります。

条件を満たす文字列が複数存在する場合は、辞書順で最も小さいものを出力します。

入出力例

入力 : Tutorial
出力 : Tutorila

入力 : onse
出力 : nose

「onse」の場合、「nose」と「ones」の2通りが考えられます。このうち「nose」の方が辞書順で小さいため、こちらを出力します。

解法のアプローチ

• まず、与えられた文字列に含まれる母音と子音の個数をそれぞれ数えます。

• 両者の個数の差が1より大きい場合（差が2以上の場合）は、交互配置が不可能なので「Not Possible」を返します。

• 母音の方が多い場合は、最初の母音から始めて残りの文字列に対して再帰的に処理を行います。

• 子音の方が多い場合は、最初の子音から始めて残りの文字列に対して再帰的に処理を行います。

• 母音と子音の個数が同じ場合は、先頭の母音と先頭の子音を比較し、小さい方（辞書順で先に来る方）から文字列を構築します。

C++による実装例

// 母音と子音を交互に並べた文字列を生成するC++プログラム
#include <bits/stdc++.h>
using namespace std;

// 文字 'ch1' が母音かどうかを判定する
bool isVowel(char ch1){
    if (ch1 == 'a' || ch1 == 'e' || ch1 == 'i' ||
    ch1 == 'o' || ch1 =='u')
    return true;
    return false;
}

// 母音と子音を交互に並べた文字列を構築する
// str1[0...l2-1] と str2[start...l3-1] を使用
string createAltStr(string str1, string str2,
int start1, int l1){
    string finalStr1 = "";
    // まず母音/子音の文字を追加し、
    // 続いて子音/母音の文字を追加する
    for (int i=0, j=start1; j<l1; i++, j++)
    finalStr1 = (finalStr1 + str1.at(i)) + str2.at(j);
    return finalStr1;
}

// 目的の交互文字列を見つける関数
string findAltStr(string str3){
    int nv1 = 0, nc1 = 0;
    string vstr1 = "", cstr1 = "";
    int l1 = str3.size();
    for (int i=0; i<l1; i++){
        char ch1 = str3.at(i);
        // 母音を数え、母音文字列を更新する
        if (isVowel(ch1)){
        nv1++;
        vstr1 = vstr1 + ch1;
    }
    // 子音を数え、子音文字列を更新する
    else{
            nc1++;
            cstr1 = cstr1 + ch1;
        }
    }
    // 条件を満たす文字列を構築できない場合
    if (abs(nv1-nc1) >= 2)
    return "no such string";
    // 母音文字列の先頭文字を使い、
    // cstr1[0...nc1-1] と vstr1[1...nv1-1] で
    // 交互文字列を構築する
    if (nv1 > nc1)
    return (vstr1.at(0) + createAltStr(cstr1, vstr1, 1, nv1));
    // 子音文字列の先頭文字を使い、
    // vstr1[0...nv1-1] と cstr1[1...nc1-1] で
    // 交互文字列を構築する
    if (nc1 > nv1)
    return (cstr1.at(0) + createAltStr(vstr1, cstr1, 1, nc1));
    // 母音と子音の文字列が
    // 同じ長さの場合は、
    // 小さい方の文字から構築を開始する
    if (cstr1.at(0) < vstr1.at(0))
    return createAltStr(cstr1, vstr1, 0, nv1);
    // 母音から構築を開始する
    return createAltStr(vstr1, cstr1, 0, nc1);
}

// 動作確認用のドライバープログラム
int main(){
    string str3 = "Tutorial";
    cout<< findAltStr(str3);
    return 0;
}

実行結果

Tutorila

計算量

時間計算量は O(n) です。ここで n は文字列の長さを表します。文字列を一度走査して母音と子音を分離し、その後線形時間で交互文字列を構築するため、全体として効率的なアルゴリズムとなっています。