Mã hóa ngắn nhất từ điển từ C++ (Short Encoding of Words)

Cho danh sách từ, mã hóa thành chuỗi tham chiếu S và mảng index A. Mỗi từ đọc từ index đến '#'. Tìm độ dài S ngắn nhất.

Ví dụ

Input - ["time", "me", "bell"] Output - 10

Giải thích - S = "time#bell#", indexes = [0, 2, 5]. "me" là hậu tố của "time" nên không cần thêm.

Phương pháp tiếp cận (Trie ngược)

• Xây Trie từ cuối từ (ngược)
• Sắp xếp từ theo độ dài giảm dần
• Chèn từng từ vào Trie ngược: nếu đường đi đã tồn tại toàn bộ → từ là hậu tố của từ đã chèn, bỏ qua
• Nếu có nút mới tạo → cộng độ dài từ + 1 (cho '#')

Ví dụ code C++

#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);
        for (string& w : words) {
            int temp = insertNode(head, w);
            if (temp) ret += temp + 1;
        }
        return ret;
    }
};

int main() {
    vector<string> v = {"time", "me", "bell"};
    Solution ob;
    cout << ob.minimumLengthEncoding(v);
    return 0;
}

Kết quả

10