ตัวย่อคำที่สั้นที่สุดและไม่ซ้ำใน C++

สมมติว่าเรามีสตริง เช่น "word" ซึ่งมีตัวย่อดังนี้: ["word","1ord","w1rd","wo1d","wor1","2rd","w2d","wo2","1o1d","1or1","w1r1","1o2","2r1","3d","w3","4"] เรายังมีสตริงเป้าหมาย (target) และชุดสตริงในพจนานุกรม (dictionary) เราต้องหาตัวย่อของสตริงเป้าหมายที่มีความยาวน้อยที่สุด ซึ่งไม่ขัดแย้งกับตัวย่อของสตริงในพจนานุกรม ตัวเลขหรือตัวอักษรแต่ละตัวในตัวย่อนับเป็นความยาว 1 เช่น "a32bc" มีความยาว 4

เช่น ถ้าอินพุตคือ "apple" และ dictionary = ["blade"] ผลลัพธ์จะเป็น "a4"

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

• กำหนดอาร์เรย์ dict เก็บ bitmask ของคำในพจนานุกรมที่ต่างจาก target
• ฟังก์ชัน abbrLen(mask) คำนวณความยาวตัวย่อจาก bitmask
• ฟังก์ชัน dfs(bit, mask) ค้นหา bitmask ที่ให้ความยาวน้อยที่สุดและไม่ชนกับ dict: ถ้าความยาว >= minLen return; ตรวจสอบ mask กับทุก d ใน dict ถ้า (mask & d) == 0 หมายถึงชน -> match=false; ถ้าไม่ชนอะไรเลย อัพเดท minLen, minab; มิฉะนั้น ลองเซตบิตถัดไปที่เป็น candidate
• จาก main: สร้าง cand bitmask รวมของคำที่ต่างจาก target เรียก dfs(1,0) แล้วสร้างสตริงตัวย่อจาก minab

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#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;
    }
};
main() {
    Solution ob;
    vector v = {"blade"};
    cout << (ob.minAbbreviation("apple", v));
}

อินพุต

"apple", {"blade"}

เอาต์พุต

a4