C++で文字列の英数字略語をすべて生成する方法を解説

この記事では、与えられた文字列から「英数字略語」をすべて生成する興味深い問題を取り上げます。対象となる文字列の長さは10未満とし、考えられるすべての略語パターンを出力します。

英数字略語とは、文字と数字が混在した形式の文字列のことです。数字は「省略（スキップ）された文字数」を表します。省略される部分はいくつあっても構いませんが、隣り合う2つの省略部分が連続することはありません。例えば「HELLO」であれば、「HELL1」（末尾のOを省略）や「H2O」（ELとLを省略）といった形になります。

なお、文字列の長さを10未満に制限しているのは、省略した文字数が最大でも9（1桁）で表せるようにするためです。

アルゴリズム

この問題は再帰（バックトラッキング）を用いて解きます。各位置の文字に対して「その文字をそのまま残す」か「省略して数字に置き換える」という2つの選択肢を順に試していきます。直前がすでに数字の場合は、新しい数字を追加せずに既存の数字に1を加算する点がポイントです。

printAbbreviation(s, index, max, str) の手順は以下の通りです。

begin
    もし index が max と等しければ
        str を出力する
    end if
    str の末尾に s[index] を追加する
    printAbbreviation(s, index + 1, max, str) を呼び出す
    str から末尾の1文字を削除する
    count := 1
    もし str が空でなければ
        もし str の末尾が数字であれば
            末尾の数字に count の値を加算する
            str から末尾の1文字を削除する
        end if
    end if
    str の末尾に count を追加する
    printAbbreviation(s, index + 1, max, str) を呼び出す
end

C++による実装例

#include <iostream>
using namespace std;

void printAbbreviation(const string& s, int index, int max_index, string str) {
    if (index == max_index) { // 文字列の終端に到達したら結果を出力
        cout << str << endl;
        return;
    }
    str.push_back(s[index]); // 現在の文字を結果に追加
    printAbbreviation(s, index + 1, max_index, str); // 次のインデックスへ
    str.pop_back(); // 末尾の文字を削除
    int count = 1;
    if (!str.empty()) {
        if (isdigit(str.back())) { // 末尾が数字の場合
            count += (int)(str.back() - '0'); // その数字の値を加算
            str.pop_back(); // 末尾の文字を削除
        }
    }
    char to_char = (char)(count + '0'); // 数値を文字に変換
    str.push_back(to_char);
    printAbbreviation(s, index + 1, max_index, str); // 次のインデックスへ
}

void printCombination(string str) {
    if (!str.length()) // 文字列が空の場合は何もしない
        return;
    string str_res;
    printAbbreviation(str, 0, str.length(), str_res);
}

int main() {
    string str = "HELLO";
    printCombination(str);
}

実行結果

入力文字列を「HELLO」とした場合の出力は以下のようになります。各文字について「残す」か「省略する」かの2択があるため、長さ5の文字列では 2⁵ = 32 通りの略語が生成されます。

HELLO
HELL1
HEL1O
HEL2
HE1LO
HE1L1
HE2O
HE3
H1LLO
H1LL1
H1L1O
H1L2
H2LO
H2L1
H3O
H4
1ELLO
1ELL1
1EL1O
1EL2
1E1LO
1E1L1
1E2O
1E3
2LLO
2LL1
2L1O
2L2
3LO
3L1
4O
5

まとめ

再帰とバックトラッキングを組み合わせることで、各文字を「残す」か「省略する」かを全探索し、すべての英数字略語を効率よく列挙できます。長さnの文字列に対して生成される略語の総数は 2ⁿ 通りとなり、出力の先頭には元の文字列そのもの、最後には全文字を省略した数字が現れる規則性も確認できます。