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, ]