C++で単語の略語を生成するアルゴリズム（トライ木による実装）

本記事では、n個の一意な文字列からなる配列が与えられたとき、以下のルールに従って各単語に対して可能な限り短い略語を生成する問題をC++で解く方法を解説します。

問題のルール

• 略語は「最初の1文字 + 省略された文字数 + 最後の1文字」の形式で表します。
• 複数の単語が同じ略語になってしまう衝突（conflict）が発生した場合は、先頭1文字だけではなくより長いプレフィックス（接頭辞）を使うことで、単語から略語への対応が一意になるまで調整します。
• 略語化しても元の単語より短くならない場合は、元の単語をそのまま使用します。

入力例と出力例

たとえば、次のような入力が与えられたとします。

["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]

この場合の出力は以下のようになります。

["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

「like」は「l2e」、「internet」は「i6t」と短縮される一方、「god」や「me」のように短い単語はそのまま残ります。また「internal」「interval」「intension」「intrusion」は同じ「i6t」〜「i8n」系の略語候補で衝突するため、プレフィックスを伸ばして一意化されています。

解法のアプローチ：トライ木（Trie）で衝突を解消

この問題を効率的に解くには、トライ木を活用します。大まかな流れは次のとおりです。

1. ノード構造体の定義： 各ノードは通過した単語数を記録するカウンタ cnt と、26個の子ノード（アルファベット対応）を持つ配列を持ちます。
2. freeNode() 関数： 再帰的に子ノードを解放し、メモリリークを防ぎます。
3. insertNode() 関数： 単語をトライ木に挿入します。経路上の各ノードの cnt をインクリメントし、その文字を共有している単語の数を記録します。
4. abbreviate() 関数： 単語を先頭から走査し、cnt == 1（＝そのプレフィックスを持つ単語が自分だけ）になった位置で打ち切り、そこまでのプレフィックス＋省略文字数＋末尾文字からなる略語を返します。
5. wordsAbbreviation() 関数（本体）： まず全単語を初期略語でグループ分けし、グループ内に複数の単語がある場合のみトライ木を構築して衝突を解消します。

処理の詳細な手順

• 辞書内の各単語について、初期略語 x を計算します（省略文字数が1以下なら元の単語のまま）。同じ略語を持つ単語のインデックスをマップ m[x] にまとめます。
• マップの各エントリを走査し、登録件数が1件以下のグループはスキップします（衝突がないため）。
• 衝突のあるグループについては、新しいトライ木を作成し、グループ内の全単語を挿入します。
• 再度グループ内の各単語に対して abbreviate() を呼び出し、結果を答えの配列に書き込みます。
• 使用済みのトライ木は freeNode() で解放してから次へ進みます。

この方法により、衝突が発生した単語群だけを対象に最小限の計算で一意な最短略語を求められます。

C++での実装例

以下に、上記のアルゴリズムを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;
}
struct Node{
   int cnt;
   Node* child[26];
   Node(){
      cnt = 0;
      for(int i = 0; i < 26; i++)child[i] = NULL;
   }
};
class Solution {
   public:
   void freeNode(Node* head){
      if (!head)
      return;
      for (int i = 0; i < 26; i++) {
         freeNode(head->child[i]);
      }
      delete head;
   }
   void insertNode(Node* node, string s){
      Node* curr = node;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (!node->child[x - 'a']) {
            node->child[x - 'a'] = new Node();
         }
         node = node->child[x - 'a'];
         node->cnt++;
      }
   }
   string abbreviate(Node* node, string s){
      string ret = "";
      Node* curr = node;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         curr = curr->child[x - 'a'];
         if (curr->cnt == 1) {
            int rem = s.size() - (i + 2);
            ret = rem <= 1 ? s : s.substr(0, i + 1) + to_string(rem) + s.back();
            break;
         }
      }
      return ret;
   }
   vector<string> wordsAbbreviation(vector<string>& dict) {
      int n = dict.size();
      vector<string> ret(n);
      map<string, vector<int> > m;
      for (int i = 0; i < n; i++) {
         string word = dict[i];
         int rem = word.size() - 2;
         string x = rem <= 1 ? word : word.front() + to_string(rem) + word.back();
         m[x].push_back(i);
         ret[i] = x;
      }
      Node* head;
      map<string, vector<int> >::iterator it = m.begin();
      while (it != m.end()) {
         if (it->second.size() <= 1) {
            it++;
            continue;
         }
         head = new Node();
         for (int i = 0; i < it->second.size(); i++) {
            int idx = it->second[i];
            insertNode(head, dict[idx]);
         }
         for (int i = 0; i < it->second.size(); i++) {
            int idx = it->second[i];
            ret[idx] = abbreviate(head, dict[idx]);
         }
         freeNode(head);
         it++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"like","god","internal","me","internet","interval","intension","face","intrusion"};
   print_vector(ob.wordsAbbreviation(v));
}

入力

{"like","god","internal","me","internet","interval","intension","face","intrusion"}

出力

[l2e, god, internal, me, i6t, interval, inte4n, f2e, intr4n]

まとめ

この実装では、まず初期略語で単語をグループ化し、衝突が起きたグループだけにトライ木を適用することで効率化しています。トライ木の各ノードが「そのプレフィックスを共有する単語数」を保持しているため、cnt == 1 になった時点でその単語が一意に識別でき、そこまでのプレフィックスを使った最短略語が確定します。計算量は O(C log N) 程度（C は全単語の総文字数）となり、大量の単語を扱う場合にも実用的なアプローチです。