n개의 고유한 문자열 배열이 있다고 가정하고 아래 규칙에 따라 모든 단어에 대해 가능한 최소한의 약어를 생성해야 합니다.
-
첫 번째 문자부터 시작하여 약어된 문자 수, 그 뒤에 마지막 문자가 옵니다.
-
충돌이 발견되고 동일한 약어를 공유하는 단어가 두 개 이상인 경우 단어 간에 맵이 고유해질 때까지 첫 번째 문자 대신 더 긴 접두어를 사용할 수 있습니다.
-
약어가 단어를 더 짧게 만들지 않으면 원래대로 유지하십시오.
따라서 입력이 ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]과 같으면 출력은 다음과 같습니다.
["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
노드 구조를 정의하십시오. cnt와 26개의 자식 노드 배열이 있으며 처음에는 모두 비어 있습니다.
-
freeNode() 함수를 정의하면 머리가 필요합니다.
-
헤드가 null이면 -
-
반환
-
-
initialize i :=0의 경우, i <26일 때 업데이트(i를 1만큼 증가), 수행
-
freeNode(머리의 자식[i])
-
-
머리 삭제
-
insertNode() 함수를 정의하면 node, s,
가 사용됩니다. -
curr =노드
-
initialize i :=0의 경우, i
-
x :=s[i]
-
노드의 자식[x - 'a']가 null이 아니면
-
노드의 자식[x - 'a'] :=새 노드
-
-
노드 :=노드의 자식[x - 'a']
-
노드의 cnt를 1 증가
-
-
abbreviate() 함수를 정의하면 node, s,
가 필요합니다. -
ret :=빈 문자열
-
curr =노드
-
initialize i :=0의 경우, i
-
x :=s[i]
-
curr :=curr의 자식[x - 'a']
-
curr의 cnt가 1과 같으면 -
-
rem :=s의 크기
-
ret :=(rem <=1이면 s, 그렇지 않으면 인덱스 0에서 i까지 s의 하위 문자열이 s의 마지막 요소를 문자열로 연결하여 rem을 연결
-
루프에서 나오세요
-
-
-
리턴 렛
-
wordAbbreviation() 함수를 정의하면 배열 사전이 필요합니다.
-
n :=dict의 크기
-
n
크기의 배열 ret 정의 -
하나의 mapm 정의
-
initialize i :=0의 경우, i
-
단어 :=사전[i]
-
rem :=단어 크기 - 2
-
x :=(rem <=1이면 단어, 그렇지 않으면 단어의 첫 번째 요소 연결 rem 단어의 마지막 요소 연결)
-
m[x]
끝에 i 삽입 -
ret[i] :=x
-
-
m 단위의 각 키-값 쌍에 대해 다음을 수행합니다. -
-
값의 크기가 <=1이면 -
-
(1씩 증가)
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
헤드 :=새 노드
-
for initialize i :=0, i <값의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
-
idx :=그것의 값[i]
-
insertNode(head, dict[idx])
-
-
for initialize i :=0, i <값의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
-
idx :=그것의 값[i]
-
ret[idx] :=abbreviate(head, dict[idx])
-
-
freeNode(헤드)
-
(1씩 증가)
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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, ]