C++で単語の一般化された略語を生成するアルゴリズムを解説

ある単語が与えられたとき、その単語の一般化された略語（generalized abbreviations）をすべて生成する関数を定義することを考えます。

一般化された略語とは、単語の中の任意の連続する文字を、その文字数を表す数字に置き換えたものです。例えば、入力が "word" の場合、出力は次のようになります。

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

このように、元の単語そのものも含め、各位置の文字を「そのまま残す」か「数字に置き換える」かの組み合わせによって、すべての略語パターンが生成されます。

解法のアプローチ

この問題は、バックトラッキング（backtracking）を用いた再帰的な手法で解くことができます。各文字について選択肢を一つずつ試しながら、すべての組み合わせを体系的に探索していきます。

具体的な手順は以下の通りです。

1. 結果を格納する配列 ret を定義します。
2. 関数 solve() を定義します。引数として文字列 s と現在のインデックス idx を受け取ります。
3. idx が s のサイズ以上になった場合：
   • s を ret の末尾に追加し、処理を終了して戻ります。
4. y := s の先頭から idx - 1 までの部分文字列を取得します。
5. i := y のサイズ - 1 とします。
6. num := 空文字列で初期化します。
7. i >= 0 かつ y[i] が '0' ～ '9' の数字である間、以下を繰り返します。
   • num := y[i] + num（数字を前方に連結）
   • i を 1 減らします。
8. i が y のサイズ - 1 と等しくない場合（＝直前の位置に数字が存在する場合）：
   • 既存の数字に 1 を加えた新しい文字列を構築します。具体的には、s の先頭部分 ＋（num + 1 の文字列）＋ s の残りの部分を連結します。
   • s1 :=（num + 1）の文字列表現
   • s2 := num の文字列表現
   • s1 と s2 の桁数が同じ場合は solve(ret, idx) を呼び出し、桁数が変わった場合は solve(ret, idx + 1) を呼び出します。
9. それ以外の場合（＝直前の位置に数字がない場合）：
   • prev := s[idx]（現在の文字を退避）
   • s[idx] := '1'（現在の位置を数字 '1' に置き換え）
   • solve(s, idx + 1) を呼び出します。
   • s[idx] := prev（元の文字に復元＝バックトラック）
10. 最後に、現在の文字をそのまま残すケースとして solve(s, idx + 1) を呼び出します。

メイン関数では、solve(word, 0) を呼び出した後、ret を返すだけで完成です。

実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<string> ret;
   void solve(string s, int idx){
      if (idx >= s.size()) {
         ret.push_back(s);
         return;
      }
      string y = s.substr(0, idx);
      int i = y.size() - 1;
      string num = "";
      while (i >= 0 && y[i] <= '9' && y[i] >= '0') {
         num = y[i] + num;
         i--;
      }
      if (i != y.size() - 1) {
         string ret = s.substr(0, idx - (y.size() - 1 - i)) + to_string(stoi(num) + 1) + s.substr(idx + 1);
         string s1 = to_string(stoi(num) + 1);
         string s2 = to_string(stoi(num));
         if (s1.size() == s2.size())
            solve(ret, idx);
         else
            solve(ret, idx + 1);
      }
      else {
         char prev = s[idx];
         s[idx] = '1';
         solve(s, idx + 1);
         s[idx] = prev;
      }
      solve(s, idx + 1);
   }
   vector<string> generateAbbreviations(string word){
      solve(word, 0);
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.generateAbbreviations("hello"));
}

入力

hello

出力

[5, 4o, 3l1, 3lo, 2l2, 2l1o, 2ll1, 2llo, 1e3, 1e2o, 1e1l1, 1e1lo, 1el2, 1el1o, 1ell1, 1ello, h4, h3o, h2l1, h2lo, h1l2, h1l1o, h1ll1, h1llo, he3, he2o, he1l1, he1lo, hel2, hel1o, hell1, hello]

まとめ

このアルゴリズムでは、各文字位置ごとに「文字を残す」か「数字に置き換える」かの選択を再帰的に行うことで、すべての一般化略語を網羅的に生成しています。特に重要なポイントは、直前の位置にすでに数字が存在する場合、新たに '1' を挿入するのではなく既存の数字をインクリメントすることで、連続する文字数を正しく表現できる点です。

計算量については、各文字位置で2通りの選択肢が存在するため、全体の時間計算量は O(2ⁿ)（n は文字数）となります。このため、非常に長い単語に対しては生成される略語の数が急激に増える点に注意が必要です。