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