Mã hóa ngắn của từ trong C ++

Giả sử chúng ta có một danh sách các từ, chúng ta có thể mã hóa nó bằng cách viết một chuỗi tham chiếu S và một danh sách các chỉ mục A. Vì vậy, chẳng hạn, chúng ta hãy xem xét danh sách các từ có phải là ["time", "me", "bell" không. ], thì chúng ta có thể viết nó là S ="time # bell #" và indexes =[0, 2, 5]. Ở đây đối với mỗi chỉ mục, chúng tôi sẽ khôi phục từ bằng cách đọc từ chuỗi tham chiếu từ chỉ mục đó cho đến khi chúng tôi đạt đến ký hiệu "#".

Vì vậy, chúng ta phải tìm độ dài của chuỗi tham chiếu ngắn nhất S có thể mã hóa các từ đã cho là bao nhiêu? Vì vậy, đối với ví dụ đã cho, đầu ra sẽ là 10.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định phương thức insertNode, phương thức này sẽ lấy head và string s
curr:=head, flag:=false.
cho tôi trong phạm vi kích thước từ s-1 xuống 0
- x:=s [i]
- nếu m [x] của curr là null, thì hãy đặt flat:=true và tạo một nút mới, thành m [x] của curr.
- curr:=m [x] of curr
trả về kích thước của s khi cờ là true, ngược lại là 0
Từ phương pháp chính, hãy thực hiện như sau -
ret:=0, head:=nút mới
sắp xếp mảng từ dựa trên độ dài của chúng
n:=kích thước của từ
cho tôi trong phạm vi từ 0 đến n - 1
- temp:=insertNode (head, words [i])
- nếu nhiệt độ khác 0, thì ret:=ret + temp + 1
trả lời lại.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

["time", "me", "bell"]

Mã hóa ngắn của từ trong C ++

Ví dụ

Đầu vào

Đầu ra