C ++中的最小唯一单词缩写

假设我们有一个字符串，例如“ word”，其中包含以下缩写：[“ word”，“ 1ord”，“ w1rd”，“ wo1d”，“ wor1”，“ 2rd”，“ w2d”，“ wo2”， “ 1o1d”，“ 1or1”，“ w1r1”，“ 1o2”，“ 2r1”，“ 3d”，“ w3”，“ 4”]]。我们在字典中也有一个目标字符串和一组字符串，我们必须找到该目标字符串的缩写，且长度要尽可能短，以免与字典中字符串的缩写冲突。在这里，缩写中的每个数字或字母都被认为是length =1。因此，作为示例，缩写“ a32bc”的长度为4。

因此，如果输入就像“苹果”，而字典是[“刀片”]，那么输出将是“ a4”

为了解决这个问题，我们将遵循以下步骤-

• 定义数组字典

• 定义一个函数abbrLen()，它将带有掩码，

• ret：= n

• 对于初始化b：= 3，当b <bn时，更新b << = 1，执行-

• （将retret减少1）

• 如果（mask AND b）等于0，则-

• 返回ret

• 定义一个函数dfs()，将需要位，掩码，

• len：= abbrLen（掩码）

• 如果len> = minLen，则-

• 返回

• 匹配：= true

• 对于字典中的每个d，执行-

• 匹配：=否

• 从循环中出来

• 如果（mask AND d）等于0，则-

• 如果match为非零，则-

• minLen：= len

• minab：=面膜

• 否则-

• 如果（cand AND b）不等于0，则-

• dfs（b * 2，遮罩或b）

• 对于初始化b：=位，当b <bn时，更新b：= b * 2，执行-

• 从主要方法中执行以下操作-

• ret：=空字符串

• n：=目标大小

• bn：= 2 ^ n

• 坎德：= 0

• minLen：= inf

• 对于字典中的每个s-

• 如果s [i]不等于target [i]，则-

• 单词：=单词OR（2 ^ i）

• 忽略以下部分，跳至下一个迭代

• 如果s的大小不等于n，则-

• 字：= 0

• 对于初始化i：= 0，当i <s的大小时，更新（将i增加1），执行-

• 在字典末尾插入单词

• cand：= cand OR word

• dfs(1,0)

• 对于初始化i：= 0，当i <n时-

• j：=我

• 而（i <n和（minab AND 2 ^ i）等于0），-

• ret：= ret级联(i-j)

• （将i增加1）

• ret：= ret +目标[i]

• （将i增加1）

• 如果（minab AND 2 ^ i）不等于0，则-

• 除此以外

• 返回ret

例  

让我们看下面的实现以更好地理解-

#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