Short Encoding of Words: การเข้ารหัสสตริงสั้นที่สุดใน C++

ปัญหา

กำหนด List ของ Words เข้ารหัสโดยสตริงอ้างอิง S และ Index Array A โดยแต่ละ Word อ่านจาก S เริ่มที่ Index จนเจอ #

หา ความยาวสั้นที่สุดของ S

ตัวอย่าง: ["time", "me", "bell"] → S = "time#bell#" (ความยาว 10) Index = [0, 2, 5]

ข้อสังเกตสำคัญ

ถ้า Word A เป็น Suffix ของ Word B → A ไม่ต้องใส่ใน S แยก (อยู่ใน B แล้ว)

→ ปัญหา = หา Words ที่ ไม่ใช่ Suffix ของ Word อื่น รวมความยาว + 1 (สำหรับ #)

แนวคิด: Trie (Prefix Tree) บน Reversed Words

1. Reverse ทุก Word (Suffix → Prefix)
2. Insert ลง Trie
3. นับเฉพาะ Word ที่สร้าง Node ใหม่ (ไม่ใช่ Prefix ของ Word อื่น)

โค้ด C++

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

struct Node {
    unordered_map<char, Node*> children;
};

class Solution {
    static bool cmpLen(const string& a, const string& b) {
        return a.size() > b.size();  // เรียงยาวไปสั้น
    }
    
    int insertNode(Node* root, const string& s) {
        Node* curr = root;
        bool isNew = false;
        for (int i = s.size() - 1; i >= 0; i--) {
            char c = s[i];
            if (!curr->children.count(c)) {
                isNew = true;
                curr->children[c] = new Node();
            }
            curr = curr->children[c];
        }
        return isNew ? s.size() : 0;
    }
    
public:
    int minimumLengthEncoding(vector<string>& words) {
        sort(words.begin(), words.end(), cmpLen);
        Node* root = new Node();
        int ans = 0;
        
        for (const string& w : words) {
            int added = insertNode(root, w);
            if (added > 0) ans += added + 1;  // +1 for '#'
        }
        return ans;
    }
};

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

วิธีอีกวิธี: Hash Set (Simpler)

int minimumLengthEncoding(vector<string>& words) {
    unordered_set<string> good(words.begin(), words.end());
    for (const string& w : words) {
        for (int i = 1; i < w.size(); i++) {
            good.erase(w.substr(i));  // ลบ Suffix ทั้งหมด
        }
    }
    int ans = 0;
    for (const string& w : good) ans += w.size() + 1;
    return ans;
}

ความซับซ้อน

Input / Output

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