단어 목록이 있다고 가정하고 참조 문자열 S와 색인 목록 A를 작성하여 인코딩할 수 있습니다. 예를 들어 단어 목록이 ["time", "me", "bell" ], S ="time#bell#" 및 인덱스 =[0, 2, 5]로 쓸 수 있습니다. 여기에서 각 인덱스에 대해 "#" 기호에 도달할 때까지 해당 인덱스의 참조 문자열에서 읽어 단어를 복구합니다.
따라서 주어진 단어를 인코딩하는 가능한 가장 짧은 참조 문자열 S의 길이를 찾아야 합니다. 따라서 주어진 예에서 출력은 10이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- insertNode 메서드를 정의합니다. 이 메서드는 헤드와 문자열을 사용합니다.
- curr :=head, flag :=false.
- i의 경우 s – 1부터 0까지 크기 범위
- x :=s[i]
- curr의 m[x]가 null이면 flat :=true로 설정하고 curr의 m[x]에 새 노드를 만듭니다.
- curr :=m[x] of curr
- 플래그가 true이면 s의 크기를 반환하고 그렇지 않으면 0
- 메인 방법에서 다음을 수행하십시오. -
- ret :=0, head :=새 노드
- 길이에 따라 단어 배열 정렬
- n :=단어 크기
- 0 ~ n – 1 범위의 i에 대해
- temp :=insertNode(head, words[i])
- temp가 0이 아니면 ret :=ret + temp + 1
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
struct Node{
map <char, Node*> m;
};
class Solution {
public:
static bool cmp(string a, string b){
return a.size() > b.size();
}
int insertNode(Node* head, string s){
Node* curr = head;
bool flag = false;
for(int i = s.size() - 1; i >= 0; i--){
char x = s[i];
if(!curr->m[x]){
flag = true;
curr->m[x] = new Node();
}
curr = curr->m[x];
}
return flag? (int)s.size() : 0;
}
int minimumLengthEncoding(vector<string>& words) {
int ret = 0;
Node* head = new Node();
sort(words.begin(), words.end(), cmp);
int n = words.size();
for(int i = 0; i < n; i++){
int temp= insertNode(head, words[i]);
if(temp){
ret += (temp + 1);
}
}
return ret;
}
};
main(){
vector<string> v = {"time", "me", "bell"};
Solution ob;
cout << (ob.minimumLengthEncoding(v));
} 입력
["time", "me", "bell"]
출력
10