คำย่อที่ไม่ซ้ำขั้นต่ำใน C ++

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

ดังนั้น หากอินพุตเป็นเหมือน "apple" และพจนานุกรมคือ ["blade"] เอาต์พุตจะเป็น "a4"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนด dict อาร์เรย์

• กำหนดฟังก์ชัน abbrLen() ซึ่งจะเป็นการปิดบัง

• ret :=n

• สำหรับการเริ่มต้น b :=3 เมื่อ b

  • ถ้า (mask AND b) เท่ากับ 0 แล้ว −

    • (ลดหย่อน 1)

• รีเทิร์น

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้เวลาบิต มาสก์

• len :=abbrLen(หน้ากาก)

• ถ้า len>=minLen แล้ว −

  • กลับ

• ตรงกัน :=จริง

• สำหรับแต่ละ d ใน dict ทำ -

  • ถ้า (mask AND d) เท่ากับ 0 แล้ว −

    • ตรงกัน :=เท็จ

    • ออกจากวง

• หากการจับคู่ไม่เป็นศูนย์ −

  • minLen :=เลน

  • มินาบ :=หน้ากาก

• มิฉะนั้น −

  • สำหรับการเริ่มต้น b :=บิตเมื่อ b

    • ถ้า (แคน AND b) ไม่เท่ากับ 0 แล้ว −

      • dfs(b*2, mask OR b)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ret :=สตริงว่าง

• n :=ขนาดของเป้าหมาย

• bn :=2^n

• แคน :=0

• minLen :=inf

• สำหรับแต่ละ s ในพจนานุกรม -

  • ถ้าขนาดของ s ไม่เท่ากับ n แล้ว −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • คำ :=0

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • ถ้า s[i] ไม่เท่ากับเป้าหมาย[i] ดังนั้น −

      • word :=คำ OR (2^i)

  • ใส่คำต่อท้าย dict

  • cand :=cand OR word

• dfs(1, 0)

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน

  • ถ้า (minab AND 2^i) ไม่เท่ากับ 0 แล้ว −

    • ret :=ret + เป้าหมาย[i]

    • (เพิ่ม i ขึ้น 1)

  • มิฉะนั้น

    • เจ :=ฉัน

    • ในขณะที่ (i

      • (เพิ่ม i ขึ้น 1)

    • ret :=ret concatenate (i - j)

• รีเทิร์น

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int n, cand, bn, minLen, minab;
   vector<int> 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<string> &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<string> v = {"blade"};
   cout << (ob.minAbbreviation("apple",v));
}

อินพุต

"apple",{"blade"}

ผลลัพธ์

a4