C++での単語の略語

n個の一意の文字列の配列があるとすると、以下のルールに従って、すべての単語に対して可能な限り最小限の略語を生成する必要があります。

• 最初の文字から始まり、省略された文字数、最後の文字が続きます。

• 競合が見つかり、複数の単語が同じ略語を共有している場合は、単語から略語へのマップが一意になるまで、最初の文字だけでなく、より長いプレフィックスを使用できます。

• 略語で単語が短くならない場合は、元の単語のままにしてください。

したがって、入力が["like"、 "god"、 "internal"、 "me"、 "internet"、 "interval"、 "intension"、 "face"、 "intrusion"]の場合、出力は次のようになります。

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

これを解決するには、次の手順に従います-

• ノード構造を定義します。cntと26の子ノードの配列があり、最初はすべて空です。

• 関数freeNode（）を定義します。これは頭に浮かぶでしょう

• ヘッドがヌルの場合、-

  • 戻る

• 初期化i：=0の場合、i <26の場合、更新（iを1増やします）、実行

  • freeNode（頭の子[i]）

• 頭を削除

• 関数insertNode（）を定義します。これは、ノードs、

  を取ります。

• curr=ノード

• 初期化i：=0の場合、i

  • x：=s [i]

  • ノードのchild[x-'a']がnullでない場合、

    • node：=新しいノードのchild [x-'a']

  • node：=node

    のchild[x-'a']

  • ノードのcntを1増やします

• 関数brafter（）を定義します。これは、ノードs、

  を取ります。

• ret：=空白の文字列

• curr=ノード

• 初期化i：=0の場合、i

  • x：=s [i]

  • curr：=currの子[x-'a']

  • currのcntが1と同じ場合、-

    • rem：=sのサイズ

    • ret：=（rem <=1の場合はs、それ以外の場合はインデックス0からiまでのsの部分文字列はsの最後の要素を連結する文字列としてremを連結します

    • ループから出てきます

• retを返す

• 関数wordsAbbreviation（）を定義します。これには、配列dictが必要です。

• n：=dictのサイズ

• サイズnの配列retを定義します

• 1つのmapmを定義する

• 初期化i：=0の場合、i

  • 単語：=dict [i]

  • rem：=単語のサイズ-2

  • x：=（rem <=1の場合は単語、それ以外の場合は単語の最初の要素を連結しますremは単語の最後の要素を連結します）

  • m [x]

    の最後にiを挿入します

  • ret [i]：=x

• キーと値のペアごとに、mでそれを実行します-

  • その値のサイズが<=1の場合、-

    • （1つ増やします）

    • 次の部分を無視し、次の反復にスキップします

  • head：=新しいノード

  • 初期化i：=0の場合、i <値のサイズの場合、更新（iを1増やします）、実行-

    • idx：=その値[i]

    • insertNode（head、dict [idx]）

  • 初期化i：=0の場合、i <値のサイズの場合、更新（iを1増やします）、実行-

    • idx：=その値[i]

    • ret [idx]：=override（head、dict [idx]）

  • freeNode（head）

  • （1つ増やします）

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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, ]