数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 中的单词缩写
假设我们有一个包含 n 个唯一字符串的数组，我们必须根据以下规则为每个单词生成尽可能短的缩写。
从第一个字符开始，然后是缩写的字符数，最后是最后一个字符。
如果我们发现任何冲突，即多个单词共享相同的缩写，则可以使用更长的前缀代替仅第一个字符，直到将单词到缩写的映射变得唯一。
当缩写没有使单词变短时，则保留其原始形式。
因此，如果输入类似于 ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]，则输出将是
["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
为了解决这个问题，我们将遵循以下步骤：
定义一个节点结构，它具有 cnt 和一个包含 26 个子节点的数组，最初所有子节点都是空的。
定义一个函数 freeNode()，它将接受 head 参数。
如果 head 为空，则：
返回
对于初始化 i := 0，当 i < 26 时，更新 (i 增加 1)，执行：
freeNode(head 的 child[i])
删除 head
定义一个函数 insertNode()，它将接受 node 和 s 参数。
curr = node
对于初始化 i := 0，当 i < s 的大小，更新 (i 增加 1)，执行：
x := s[i]
如果 node 的 child[x - 'a'] 不为空，则
node 的 child[x - 'a'] := 一个新节点
node := node 的 child[x - 'a']
将 node 的 cnt 增加 1
定义一个函数 abbreviate()，它将接受 node 和 s 参数。
ret := 空字符串
curr = node
对于初始化 i := 0，当 i < s 的大小，更新 (i 增加 1)，执行：
x := s[i]
curr := curr 的 child[x - 'a']
如果 curr 的 cnt 等于 1，则：
rem := s 的大小
ret := (如果 rem <= 1，则 s，否则 s 从索引 0 到 i 的子字符串连接 rem 作为字符串连接 s 的最后一个元素
退出循环
返回 ret
定义一个函数 wordsAbbreviation()，它将接受一个数组 dict。
n := dict 的大小
定义一个大小为 n 的数组 ret
定义一个 map m
对于初始化 i := 0，当 i < n 时，更新 (i 增加 1)，执行：
word := dict[i]
rem := word 的大小 - 2
x := (如果 rem <= 1，则 word，否则 word 的第一个元素连接 rem 连接 word 的最后一个元素)
将 i 插入到 m[x] 的末尾
ret[i] := x
对于 m 中的每个键值对 it，执行：
如果 it 的值的长度 <= 1，则：
(it 增加 1)
忽略以下部分，跳到下一个迭代
head := 一个新节点
对于初始化 i := 0，当 i < it 的值的大小，更新 (i 增加 1)，执行：
idx := it 的 value[i]
insertNode(head, dict[idx])
对于初始化 i := 0，当 i < it 的值的大小，更新 (i 增加 1)，执行：
idx := it 的 value[i]
ret[idx] := abbreviate(head, dict[idx])
freeNode(head)
(it 增加 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, ]
831 次查看
