Viết tắt từ trong C ++

Giả sử chúng ta có một mảng gồm n chuỗi duy nhất, Chúng ta phải tạo ra các chữ viết tắt tối thiểu có thể có cho mỗi từ tuân theo các quy tắc dưới đây.

• Bắt đầu bằng ký tự đầu tiên và sau đó là số ký tự được viết tắt, theo sau là ký tự cuối cùng.

• Nếu chúng tôi tìm thấy bất kỳ xung đột nào và có nhiều hơn một từ có chung một chữ viết tắt, thì một tiền tố dài hơn có thể được sử dụng thay vì chỉ ký tự đầu tiên cho đến khi làm cho bản đồ từ từ này sang chữ viết tắt trở thành duy nhất.

• Khi viết tắt không làm cho từ ngắn hơn, thì hãy giữ nguyên từ đó.

Vì vậy, nếu đầu vào là ["like", "god", "nội bộ", "tôi", "internet", "khoảng", "intension", "mặt", "xâm nhập"], thì đầu ra sẽ là

["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

• Xác định cấu trúc nút, nó có cnt và một mảng gồm 26 nút con, ban đầu tất cả đều trống.

• Xác định một hàm freeNode (), điều này sẽ chiếm phần đầu,

• nếu đầu null, thì -

  • trở lại

• để khởi tạo i:=0, khi tôi <26, hãy cập nhật (tăng i lên 1), thực hiện

  • freeNode (con [i] of head)

• xóa đầu

• Xác định một hàm insertNode (), điều này sẽ lấy nút, s,

• curr =nút

• để khởi tạo i:=0, khi i

  • x:=s [i]

  • nếu con [x - 'a'] của nút không phải là null, thì

    • con [x - 'a'] of node:=a new node

  • nút:=con [x - 'a'] của nút

  • tăng cnt của nút lên 1

• Xác định một hàm viết tắt (), điều này sẽ lấy nút, s,

• ret:=chuỗi trống

• curr =nút

• để khởi tạo i:=0, khi i

  • x:=s [i]

  • curr:=child [x - 'a'] của curr

  • nếu cnt của curr giống với 1, thì -

    • rem:=kích thước của s

    • ret:=(nếu rem <=1, thì s, nếu không thì chuỗi con của s từ chỉ số 0 đến tôi nối rem dưới dạng chuỗi nối phần tử cuối cùng của s

    • Ra khỏi vòng lặp

• trả lại ret

• Xác định một từ chức năng Viết tắt (), điều này sẽ lấy một mảng dict,

• n:=kích thước của dict

• Xác định ret mảng có kích thước n

• Xác định một bản đồ

• để khởi tạo i:=0, khi i

  • từ:=dict [i]

  • rem:=kích thước của từ - 2

  • x:=(nếu rem <=1, thì từ, nếu không phần tử đầu tiên của từ thì nối lại phần tử cuối cùng của từ)

  • chèn i vào cuối m [x]

  • ret [i]:=x

• đối với mỗi cặp khóa-giá trị, nó bằng m, do -

  • nếu kích thước giá trị của nó là <=1, thì -

    • (tăng nó lên 1)

    • Bỏ qua phần sau, chuyển sang phần tiếp theo

  • head:=một nút mới

  • để khởi tạo i:=0, khi i

    • idx:=value [i] của nó

    • insertNode (head, dict [idx])

  • để khởi tạo i:=0, khi i

    • idx:=value [i] của nó

    • ret [idx]:=viết tắt (head, dict [idx])

  • freeNode (head)

  • (tăng nó lên 1)

• trả lại ret

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

Đầu vào

{"like","god","internal","me","internet","interval","intension","face","intrusion"}

Đầu ra

[l2e, god, internal, me, i6t, interval, inte4n, f2e, intr4n, ]