C ++中的单词缩写
假设我们有n个唯一字符串组成的数组，则必须遵循以下规则为每个单词生成尽可能小的缩写。
从第一个字符开始，然后是缩写的字符数，然后是最后一个字符。
如果我们发现任何冲突，并且有多个单词共享相同的缩写，则可以使用更长的前缀而不是仅使用第一个字符，直到使单词到缩写的映射变得唯一为止。
如果缩写没有使单词更短，则将其保留为原始字母。
因此，如果输入类似于[“like”，“god”，“internal”，“me”，“internet”，“interval”，“intent”，“face”，“intrusion”]]，那么输出将是
["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
为了解决这个问题，我们将遵循以下步骤-
定义一个节点结构，它具有cnt和26个子节点的数组，最初都为空。
定义一个功能freeNode()，这将使您受益匪浅，
如果head为null，则-
返回
对于初始化i：=0，当i<26时，更新（将i增加1），执行
freeNode（头的孩子[i]）
删除头
定义一个函数insertNode()，它将取节点s，
curr=节点
对于初始化i：=0，当i<s的大小时，更新（将i增加1），执行-
节点的child[x-'a']：=一个新节点
x：=s[i]
如果节点的child[x-'a']不为null，则
节点：=节点的孩子[x-'a']
将节点的cnt增加1
定义一个函数abbreviate()，它将取节点s，
ret：=空字符串
curr=节点
对于初始化i：=0，当i<s的大小时，更新（将i增加1），执行-
rem：=s的大小
ret：=（如果rem<=1，则为s，否则从索引0到i的s的子字符串将rem串联为字符串，将s的最后一个元素串联
从循环中出来
x：=s[i]
curr：=child的子项[x-'a']
如果curr的cnt等于1，则-
返回ret
定义一个函数wordsAbbreviation()，它将接受一个数组字典，
n：=字典大小
定义大小为n的数组ret
定义一个mapm
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
字：=字典[i]
rem：=字长-2
x：=（如果rem<=1，则为单词，否则将单词的第一个元素连接起来，而rem则连接单词的最后一个元素）
在m[x]的末尾插入i
ret[i]：=x
对于每个以m为单位的键值对，执行-
idx：=value[i]
ret[idx]：=缩写（head，dict[idx]）
idx：=value[i]
insertNode（head，dict[idx]）
（增加1）
忽略以下部分，跳至下一个迭代
如果它的值大小小于等于1，则-
头：=一个新节点
对于初始化i：=0，当i<其值的大小时，更新（将i增加1），执行-
对于初始化i：=0，当i<其值的大小时，更新（将i增加1），执行-
freeNode（头）
（增加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, ]