C ++中单词的短编码

假设我们有一个单词列表，我们可以通过写一个参考字符串S和一个索引列表A对其进行编码。例如，让我们考虑一下单词列表是否为[“ time”，“ me”，“ bell” ]，则可以将其写为S =“ time#bell#”，索引= [0，2，5]。在这里，对于每个索引，我们将通过从该索引的参考字符串中读取来恢复单词，直到到达“#”符号。

因此，我们必须找出编码给定单词的最短参考字符串S的长度是多少？因此，对于给定的示例，输出将为10。

为了解决这个问题，我们将遵循以下步骤-

• 定义insertNode方法，这将使用head和string

• curr：= head，标志：= false。

• 对于i，范围为s – 1降至0

• x：= s [i]

• 如果curr的m [x]为null，则将flat：= true设置为并创建一个新节点到curr [x]。

• curr：= m [x]的curr

• 当标志为true时，返回s的大小，否则为0

• 从主要方法中，执行以下操作-

• ret：= 0，head：=新节点

• 根据单词的长度对单词数组进行排序

• n：=字数

• 对于i，范围为0至n – 1

• temp：= insertNode（head，words [i]）

• 如果temp不为0，则ret：= ret + temp + 1

• 返回ret。

让我们看下面的实现以更好地理解-

示例

#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