C/C++で母音と子音を交互に並べる文字列再編成アルゴリズム

問題概要

文字列が与えられたとき、文字を並べ替えて母音と子音が交互に配置されるような文字列を作成するのが本記事のテーマです。もし条件を満たす並べ替えが不可能な場合は、「not possible」と出力します。

重要な制約として、母音同士の相対的な順序、および子音同士の相対的な順序は元の文字列のまま維持しなければなりません。

入力: abce
出力: abec

アルゴリズムの考え方

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

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

• 母音の方が子音より多い場合は、最初の母音を先頭に出力し、残りの文字列に対して同じ処理を再帰的に適用します。

• 子音の方が母音より多い場合は、最初の子音を先頭に出力し、残りの文字列に対して再帰的に処理します。

• 母音と子音の個数が同じ場合は、最初の母音と最初の子音を比較し、辞書順で小さい方（アルファベット順で先に来る方）を先に出力します。

C++による実装例

#include <iostream>
using namespace std;
bool isVowel(char ch) {
    if (ch == 'a' || ch == 'e' || ch == 'i' ||
        ch == 'o' || ch =='u')
    return true;
    return false;
}
string createAltStr(string str1, string str2,
int start, int l) {
    string finalStr = "";
    for (int i=0, j=start; j<l; i++, j++)
        finalStr = (finalStr + str1.at(i)) + str2.at(j);
    return finalStr;
}
string findAltStr(string str) {
    int nv = 0, nc = 0;
    string vstr = "", cstr = "";
    int l = str.size();
    for (int i=0; i<l; i++) {
        char ch = str.at(i);
        if (isVowel(ch)) {
            nv++;
            vstr = vstr + ch;
        } else {
            nc++;
            cstr = cstr + ch;
        }
    }
    if (abs(nv-nc) >= 2)
        return "no such string";
    if (nv > nc)
        return (vstr.at(0) + createAltStr(cstr, vstr, 1, nv));
    if (nc > nv)
        return (cstr.at(0) + createAltStr(vstr, cstr, 1, nc));
    if (cstr.at(0) < vstr.at(0))
        return createAltStr(cstr, vstr, 0, nv);
    return createAltStr(vstr, cstr, 0, nc);
}
int main() {
    string str = "abde";
    cout << findAltStr(str);
    return 0;
}

コードのポイント

この実装では、isVowel関数で文字が母音かどうかを判定し、母音と子音をそれぞれ別の文字列（vstrとcstr）に振り分けています。これにより元の順序が自然に保持されます。その後、createAltStr関数が2つの文字列から交互に1文字ずつ取り出して最終結果を組み立てます。個数の差が2以上ある場合は並べ替えが不可能であるため、早期に判定して返却する点も効率的です。