Rút gọn từ duy nhất ngắn nhất trong C++

Cho chuỗi "word" có các viết tắt: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]. Mỗi số hoặc chữ cái tính độ dài 1. Cho chuỗi target và từ điển, tìm viết tắt của target có độ dài nhỏ nhất không trùng với viết tắt của bất kỳ từ nào trong từ điển.

Ví dụ: target = "apple", dictionary = ["blade"] → Kết quả = "a4"

Phương pháp giải

Sử dụng bitmask độ dài n (độ dài target). Bit 1 = giữ ký tự, bit 0 = nén. Duyệt DFS các mask, tính độ dài viết tắt. Kiểm tra mask có phân biệt được với tất cả từ trong từ điển không (mask & word != 0). Tìm mask có độ dài nhỏ nhất thỏa mãn.

Ví dụ chương trình

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

class Solution {
public:
    int n, cand, bn, minLen, minab;
    vector dict;
    
    int abbrLen(int mask) {
        int ret = n;
        for (int b = 3; b < bn; b <<= 1) {
            if ((mask & b) == 0) ret--;
        }
        return ret;
    }
    
    void dfs(int bit, int mask) {
        int len = abbrLen(mask);
        if (len >= minLen) return;
        bool match = true;
        for (int d : dict) {
            if ((mask & d) == 0) { match = false; break; }
        }
        if (match) { minLen = len; minab = mask; }
        else {
            for (int b = bit; b < bn; b <<= 1) {
                if ((cand & b) != 0) dfs(b << 1, mask | b);
            }
        }
    }
    
    string minAbbreviation(string target, vector& dictionary) {
        string ret = "";
        n = target.size();
        bn = 1 << n;
        cand = 0; minLen = INT_MAX;
        for (string& s : dictionary) {
            if (s.size() != n) continue;
            int word = 0;
            for (int i = 0; i < s.size(); i++) {
                if (s[i] != target[i]) word |= (1 << i);
            }
            dict.push_back(word);
            cand |= word;
        }
        dfs(1, 0);
        for (int i = 0; i < n;) {
            if ((minab & (1 << i)) != 0) { ret += target[i]; i++; }
            else {
                int j = i;
                while (i < n && (minab & (1 << i)) == 0) i++;
                ret += to_string(i - j);
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector v = {"blade"};
    cout << ob.minAbbreviation("apple", v);
    return 0;
}

Đầu vào

"apple", {"blade"}

Đầu ra

a4