C++で文字列の大文字・小文字の全パターン（文字ケース順列）を生成する方法

英字と数字が混在する文字列が与えられたとき、文字列に含まれる各英字について大文字と小文字の両方のバージョンを組み合わせ、考えられるすべての文字列パターンを生成することを考えます。文字列が数字のみで構成されている場合は、その文字列そのものだけを返します。

例として、文字列「1ab2」が与えられた場合、生成される結果は次のようになります。

["1ab2", "1Ab2", "1aB2", "1AB2"]

解決アプローチ：再帰による全探索

この問題は再帰的なアプローチで解くことができます。基本的な考え方は以下の通りです。

• 処理を開始する位置を示すインデックスを引数として受け取ります。
• そこまでの結果を保持する一時文字列も一緒に渡します。
• インデックスが文字列の長さと一致した時点で、一時文字列を結果リストに追加して処理を終了します（再帰の終了条件）。
• 現在のインデックスの文字が小文字であれば大文字に変換したバージョンでも再帰を呼び出し、大文字であれば小文字に変換したバージョンでも再帰を呼び出します。これにより、各英字について「そのまま」と「反転」の2通りの分岐が生まれます。
• 数字の場合は変換せず、そのまま次のインデックスへ進みます。

C++での実装例

それでは、実際の実装を見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector <string> res;
    void solve(string s, int idx = 0, string temp = ""){
        if(idx == s.size()){
            res.push_back(temp);
            return;
        }
        solve(s, idx + 1, temp + s[idx]);
        int diff = 'a' - 'A';
        if(s[idx] >= 'a' && s[idx] <= 'z'){
            char x = (s[idx] - diff);
            solve(s, idx + 1, temp + x);
        }
        else if (s[idx] >= 'A' && s[idx] <= 'Z'){
            char x = (s[idx] + diff);
            solve(s, idx + 1, temp + x);
        }
    }
    vector<string> letterCasePermutation(string S) {
        res.clear();
        solve(S);
        return res;
    }
};
main(){
    Solution ob;
    print_vector(ob.letterCasePermutation("1ab2"));
    print_vector(ob.letterCasePermutation("9876"));
}

入力

"1ab2"
"9876"

出力

[1ab2, 1aB2, 1Ab2, 1AB2]
[9876]

コードのポイント

• 大文字と小文字の差分： ASCIIコードでは同じ英字の大文字と小文字の差は一定（'a' - 'A' = 32）であるため、この差分を使って簡単に相互変換できます。
• 計算量： 英字が n 個含まれる文字列の場合、組み合わせは最大 2^n 通りになるため、時間計算量は O(2^n × n) となります。
• 数字の扱い： 数字は大文字・小文字の区別がないため、分岐せずそのまま次の文字へ進みます。そのため「9876」のような数字のみの文字列では、元の文字列1つだけが結果になります。

このように、再帰を用いたシンプルな実装で、文字列中の英字の大文字・小文字に関するすべての組み合わせを効率よく列挙することができます。