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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串，例如“ 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

          以上是 C ++中的最小唯一单词缩写 的全部内容， 来源链接： utcz.com/z/334981.html

          回到顶部