411. Minimum Unique Word Abbreviation

class Solution {
private:
    vector<int> dict;
    int len, bmax, base, minMask, minLen;

    void DFS(int k, int mask) {
        int currLen = getLen(mask);
        if (currLen >= minLen) return;
        if (isunique(mask)) {
            minLen = currLen;
            minMask = mask;
            return;
        }
        for (int b = 1 << k; k < len; k++, b <<= 1)
            if (base & b) DFS(k + 1, mask | b);
        return;
    }

    int getLen(int mask) {
        int cnt = 0, cnt0 = 0;
        for (int i = 0, b = bmax; i < len; i++, b >>= 1)
            if (mask & b) cnt += (cnt0 != 0) + 1, cnt0 = 0;
                else cnt0++;
        return cnt + (cnt0 != 0);

        // int count = 0;
        // for (int b = 1; b < bn;) {
        //     if ((mask & b) == 0)
        //         for (; b < bn and (mask & b) == 0; b <<= 1);
        //     else b <<= 1;
        //     count ++;
        // }
        // return count;

        // int count = n;
        // for (int b = 3; b < bn; b <<= 1)
        //     if ((mask & b) == 0)
        //         count --;
        // return count;
    }

    bool isunique(int mask) {
        for (int d : dict)
            if (!(mask & d)) return false;
        return true;
    }

public:
    string minAbbreviation(string target, vector<string>& dictionary) {
        len = target.size(); bmax = 1 << (len - 1); base = 0;
        for (string w : dictionary) {
            if (len != w.size()) continue;
            int maskT = 0;
            for (int i = 0, b = bmax; i < len; i++, b >>= 1)
                if (w[i] != target[i]) maskT |= b;
            dict.push_back(maskT); base |= maskT;
        }


        minLen = len;
        minMask = (1 << len) - 1;
        DFS(0, 0);

        string res;int cnt0 = 0;
        for (int i = 0, b = bmax; i < len; i++, b >>= 1)
            if (minMask & b)
                res += (cnt0 ? to_string(cnt0) : "") + target[i], cnt0 = 0;
            else cnt0++;
        res += (cnt0 ? to_string(cnt0) : "");
        return res;
    }
};