คำย่อในภาษา C++

สมมติว่าเรามีอาร์เรย์ของ n สตริงที่ไม่ซ้ำกัน เราต้องสร้างตัวย่อที่เป็นไปได้น้อยที่สุดสำหรับทุกคำที่เป็นไปตามกฎด้านล่าง

• เริ่มต้นด้วยอักขระตัวแรก แล้วตามด้วยจำนวนอักขระย่อ ตามด้วยอักขระตัวสุดท้าย

• หากเราพบข้อขัดแย้งใดๆ และนั่นคือคำมากกว่าหนึ่งคำที่ใช้ตัวย่อเดียวกัน คุณสามารถใช้คำนำหน้าที่ยาวขึ้นแทนอักขระตัวแรกได้ จนกว่าการทำแผนที่จากคำหนึ่งไปอีกคำย่อจะไม่ซ้ำกัน

• เมื่อตัวย่อไม่ได้ทำให้คำสั้นลง ก็ให้ใช้คำเดิม

ดังนั้น หากอินพุตเป็นเหมือน ["ชอบ", "พระเจ้า", "ภายใน", "ฉัน", "อินเทอร์เน็ต", "ช่วง", "ความตั้งใจ", "ใบหน้า", "การบุกรุก"] ผลลัพธ์จะเป็น

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดโครงสร้างโหนด มันมี cnt และอาร์เรย์ของโหนดย่อย 26 โหนด ในขั้นต้นทั้งหมดจะว่างเปล่า

• กำหนดฟังก์ชั่น freeNode() สิ่งนี้จะเริ่มต้น

• ถ้า head null แล้ว −

  • กลับ

• สำหรับการเริ่มต้น i :=0 เมื่อ i <26 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ

  • freeNode(ลูก[i] ของศีรษะ)

• ลบหัว

• กำหนดฟังก์ชัน insertNode() ซึ่งจะใช้ node, s,

• curr =โหนด

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • x :=s[i]

  • ถ้าลูก[x - 'a'] ของโหนดไม่เป็นค่าว่าง ดังนั้น

    • ลูก[x - 'a'] ของโหนด :=โหนดใหม่

  • โหนด :=ลูก[x - 'a'] ของโหนด

  • เพิ่ม cnt ของโหนดขึ้น 1

• กำหนดฟังก์ชัน abbreviate() ซึ่งจะใช้ node, s,

• ret :=สตริงว่าง

• curr =โหนด

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • x :=s[i]

  • curr :=child[x - 'a'] ของสกุลเงิน

  • ถ้า cnt ของ curr เหมือนกับ 1 แล้ว −

    • rem :=ขนาดของ s

    • ret :=(ถ้า rem <=1 แล้ว s มิฉะนั้น สตริงย่อยของ s จากดัชนี 0 ถึง i เชื่อม rem เป็นสตริงที่เชื่อมองค์ประกอบสุดท้ายของ s

    • ออกจากวง

• รีเทิร์น

• กำหนดฟังก์ชัน wordAbbreviation() ซึ่งจะใช้ dict อาร์เรย์

• n :=ขนาดของ dict

• กำหนดขนาดของอาร์เรย์ n

• กำหนดหนึ่งแผนที่

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • word :=dict[i]

  • rem :=ขนาดคำ - 2

  • x :=(ถ้า rem <=1 แล้ว word มิฉะนั้นองค์ประกอบแรกของคำ concatenate rem concatenate องค์ประกอบสุดท้ายของคำ)

  • ใส่ i ต่อท้าย m[x]

  • ret[i] :=x

• สำหรับแต่ละคีย์-ค่าจับคู่ในหน่วย m ให้ทำ -

  • ถ้าขนาดของมันคือ <=1 แล้ว −

    • (เพิ่มขึ้นอีก 1)

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • head :=โหนดใหม่

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของค่าของมัน ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

    • idx :=value[i] ของมัน

    • insertNode(หัว, dict[idx])

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของค่าของมัน ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

    • idx :=value[i] ของมัน

    • ret[idx] :=ตัวย่อ(หัว, 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, ]