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

Mô tả bài toán

Cho mảng n chuỗi duy nhất. Tạo viết tắt tối thiểu cho mỗi từ theo quy tắc:

• Bắt đầu bằng ký tự đầu, theo sau là số ký tự bị lược bỏ, cuối cùng là ký tự cuối.
• Nếu xung đột (nhiều từ cùng viết tắt), mở rộng tiền tố cho đến khi viết tắt trở nên duy nhất.
• Nếu viết tắt không làm từ ngắn hơn, giữ nguyên từ gốc.

Ví dụ: ["like","god","internal","me","internet","interval","intension","face","intrusion"] → ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"].

Ý tưởng giải pháp (Trie)

• Xây dựng Trie để đếm số từ chia sẻ mỗi tiền tố.
• Đối với mỗi nhóm từ có cùng viết tắt ban đầu:
  • Chèn tất cả từ vào Trie, tăng bộ đếm tại mỗi nút.
  • Duyệt từng từ trên Trie, dừng tại nút đầu tiên có cnt == 1 → tiền tố đủ dài để phân biệt.
  • Tạo viết tắt từ tiền tố đó.

Ví dụ minh họa

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

void print_vector(vector<string> 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; fill(begin(child), end(child), nullptr); }
};

class Solution {
    void freeNode(Node* head) {
        if (!head) return;
        for (int i = 0; i < 26; i++) freeNode(head->child[i]);
        delete head;
    }
    void insertNode(Node* node, const string& s) {
        for (char x : s) {
            if (!node->child[x - 'a']) node->child[x - 'a'] = new Node();
            node = node->child[x - 'a'];
            node->cnt++;
        }
    }
    string abbreviate(Node* node, const string& s) {
        for (int i = 0; i < s.size(); i++) {
            node = node->child[s[i] - 'a'];
            if (node->cnt == 1) {
                int rem = s.size() - (i + 2);
                return rem <= 1 ? s : s.substr(0, i + 1) + to_string(rem) + s.back();
            }
        }
        return s;
    }
public:
    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;
        }
        for (auto& [abbr, idxs] : m) {
            if (idxs.size() <= 1) continue;
            Node* head = new Node();
            for (int idx : idxs) insertNode(head, dict[idx]);
            for (int idx : idxs) ret[idx] = abbreviate(head, dict[idx]);
            freeNode(head);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"like","god","internal","me","internet","interval","intension","face","intrusion"};
    print_vector(ob.wordsAbbreviation(v));
    return 0;
}

Đầu vào

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

Đầu ra

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