การย่อคำใน C++

ปัญหา

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

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

เช่น ถ้าผนวกเข้าเป็น ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"] ผลลัพธ์จะเป็น ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

วิธีแก้ปัญหา

1. กำหนดโครงสร้างโหนด มี cnt และอาร์เรย์โหนดลูก 26 ตัว เริ่มต้นว่าทั้งหมด
2. กำหนดฟังก์ชัน freeNode() รับ head:
   • ถ้า head เป็น null คืนค่า
   • for i := 0 ถึง 25: freeNode(child[i] ของ head)
   • delete head
3. กำหนดฟังก์ชัน insertNode() รับ node, s:
   • curr = node
   • for i := 0 ถึง size of s - 1 ทำ:
     • x := s[i]
     • ถ้า child[x - 'a'] ของ node ไม่เป็น null: child[x - 'a'] := โหนดใหม่
     • node := child[x - 'a'] ของ node
     • เพิ่ม cnt ของ node ขึ้น 1
4. กำหนดฟังก์ชัน abbreviate() รับ node, s:
   • ret := สตริงว่าง
   • curr = node
   • for i := 0 ถึง size of s - 1 ทำ:
     • x := s[i]
     • curr := child[x - 'a'] ของ curr
     • ถ้า cnt ของ curr เท่ากับ 1 แล้ว:
       • rem := size of s
       • ret := (ถ้า rem <= 1 แล้ว s มิฉะนั้น substring ของ s จากดัชนี 0 ถึง i ต่อ rem เป็นสตริง ต่อตัวอักษรสุดท้ายของ s
       • ออกจากลูป
   • คืนค่า ret
5. กำหนดฟังก์ชัน wordsAbbreviation() รับอาร์เรย์ dict:
   • n := ขนาดของ dict
   • กำหนดอาร์เรย์ ret ขนาด n
   • กำหนด map m
   • for i := 0 ถึง n-1 ทำ:
     • word := dict[i]
     • rem := size of word - 2
     • x := (ถ้า rem <= 1 แล้ว word มิฉะนั้น ตัวอักษรแรกของ word ต่อ rem ต่อตัวอักษรสุดท้ายของ word)
     • เพิ่ม i เข้าไปท้าย m[x]
     • ret[i] := x
   • สำหรับแต่ละคู่ key-value it ใน m ทำ:
     • ถ้าขนาดของ value ของ it <= 1 แล้ว: เพิ่ม it ขึ้น 1; ข้ามรอบนี้
     • head := โหนดใหม่
     • for i := 0 ถึง size of value of it - 1 ทำ:
       • idx := value[i] ของ it
       • insertNode(head, dict[idx])
     • for i := 0 ถึง size of value of it - 1 ทำ:
       • idx := value[i] ของ it
       • ret[idx] := abbreviate(head, dict[idx])
     • freeNode(head)
     • เพิ่ม it ขึ้น 1
   • คืนค่า ret

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

void print_vector(vector<auto> v){ 
    cout << "["; 
    for(int i = 0; ichild[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; 
    } 
}; 

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