Viết tắt từ duy nhất tối thiểu trong C ++

Giả sử chúng ta có một chuỗi chẳng hạn như "word" và chứa các từ viết tắt sau:["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]. Chúng ta cũng có một chuỗi đích và một tập hợp các chuỗi trong từ điển, chúng ta phải tìm chữ viết tắt của chuỗi đích này với độ dài nhỏ nhất có thể sao cho nó không mâu thuẫn với chữ viết tắt của các chuỗi trong từ điển. Ở đây mỗi số hoặc chữ cái trong chữ viết tắt được coi là length =1. Vì vậy, như một ví dụ, chữ viết tắt "a32bc" có độ dài =4.

Vì vậy, nếu đầu vào là "apple" và từ điển là ["blade"], thì đầu ra sẽ là "a4"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng dict

• Xác định một hàm abbrLen (), hàm này sẽ sử dụng mặt nạ,

• ret:=n

• để khởi tạo b:=3, khi b

  • nếu (mặt nạ VÀ b) giống 0, thì -

    • (giảm ret xuống 1)

• trả lại ret

• Xác định một hàm dfs (), điều này sẽ mất bit, mask,

• len:=abbrLen (mask)

• if len> =minLen, then -

  • trở lại

• khớp:=true

• cho mỗi d trong dict, do -

  • nếu (mặt nạ VÀ d) giống 0, thì -

    • khớp:=false

    • Ra khỏi vòng lặp

• nếu so khớp khác 0, thì -

  • minLen:=len

  • minab:=mask

• Nếu không -

  • để khởi tạo b:=bit, khi b

    • nếu (cand AND b) không bằng 0, thì -

      • dfs (b * 2, mặt nạ HOẶC b)

• Từ phương thức chính, hãy làm như sau -

• ret:=chuỗi trống

• n:=kích thước của mục tiêu

• bn:=2 ^ n

• cand:=0

• minLen:=inf

• cho mỗi s trong từ điển -

  • nếu kích thước của s không bằng n, thì -

    • Bỏ qua phần sau, chuyển sang phần tiếp theo

  • từ:=0

  • để khởi tạo i:=0, khi i

    • nếu s [i] không bằng target [i] thì -

      • từ:=từ HOẶC (2 ^ i)

  • chèn từ vào cuối dict

  • cand:=cand HOẶC từ

• dfs (1, 0)

• để khởi tạo i:=0, when i

  • nếu (minab AND 2 ^ i) không bằng 0, thì -

    • ret:=ret + target [i]

    • (tăng tôi lên 1)

  • Nếu không

    • j:=i

    • while (i

      • (tăng tôi lên 1)

    • ret:=ret concatenate (i - j)

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

"apple",{"blade"}

Đầu ra

a4