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