C++での単語の短いエンコーディング

単語のリストがあるとすると、参照文字列SとインデックスAのリストを記述してエンコードできます。たとえば、単語のリストが["time"、 "me"、"bell"であるかどうかを考えてみましょう。 ]の場合、S ="time＃bell＃"およびindexes =[0、2、5]と書くことができます。ここでは、インデックスごとに、「＃」記号に到達するまで、そのインデックスの参照文字列から読み取ることで単語を復元します。

それで、与えられた単語をエンコードする可能な最短の参照文字列Sの長さを見つける必要がありますか？したがって、与えられた例では、出力は10になります。

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

• insertNodeメソッドを定義します。これには頭と文字列が必要です
• curr：=ヘッド、フラグ：=false。
• s –1から0までの範囲サイズのiの場合
  • x：=s [i]
  • currのm[x]がnullの場合、flat：=trueに設定し、currのm[x]に新しいノードを作成します。
  • curr：=m [x] of curr
• フラグがtrueの場合はsのサイズを返し、それ以外の場合は0を返します
• メインの方法から、次の手順を実行します-
• ret：=0、head：=new node
• 長さに基づいて単語配列を並べ替える
• n：=単語のサイズ
• 0からn–1の範囲のiの場合
  • temp：=insertNode（head、words [i]）
  • tempが0以外の場合、ret：=ret + temp + 1
• returnret。

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

例

#include <bits/stdc++.h>
using namespace std;
struct Node{
   map <char, Node*> m;
};
class Solution {
   public:
   static bool cmp(string a, string b){
      return a.size() > b.size();
   }
   int insertNode(Node* head, string s){
      Node* curr = head;
      bool flag = false;
      for(int i = s.size() - 1; i >= 0; i--){
         char x = s[i];
         if(!curr->m[x]){
            flag = true;
            curr->m[x] = new Node();
         }
         curr = curr->m[x];
      }
      return flag? (int)s.size() : 0;
   }
   int minimumLengthEncoding(vector<string>& words) {
      int ret = 0;
      Node* head = new Node();
      sort(words.begin(), words.end(), cmp);
      int n = words.size();
      for(int i = 0; i < n; i++){
         int temp= insertNode(head, words[i]);
         if(temp){
            ret += (temp + 1);
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"time", "me", "bell"};
   Solution ob;
   cout << (ob.minimumLengthEncoding(v));
}

入力

["time", "me", "bell"]

出力

10