C++での最小の一意の単語の略語

「word」などの文字列があり、次の略語が含まれているとします。["word"、 "1ord"、 "w1rd"、 "wo1d"、 "wor1"、 "2rd"、 "w2d"、 "wo2"、 「1o1d」、「1or1」、「w1r1」、「1o2」、「2r1」、「3d」、「w3」、「4」]。また、辞書にはターゲット文字列と文字列のセットがあります。辞書内の文字列の略語と競合しないように、可能な限り短い長さのこのターゲット文字列の略語を見つける必要があります。ここでは、略語の各数字または文字は長さ=1と見なされます。したがって、例として、略語「a32bc」の長さは4です。

したがって、入力が「apple」のようで、辞書が["blade"]の場合、出力は「a4」になります

これを解決するには、次の手順に従います-

• 配列辞書を定義する

• 関数abbrLen（）を定義します。これはマスクを取ります

• ret：=n

• 初期化b：=3の場合、b

  • （マスクAND b）が0と同じ場合、-

    • （retを1減らします）

• retを返す

• 関数dfs（）を定義します。これにはビット、マスク、

  が必要です。

• len：=abbrLen（mask）

• len> =minLenの場合、-

  • 戻る

• 一致：=true

• dictの各dについて、次のようにします-

  • （マスクAND d）が0と同じ場合、-

    • 一致：=false

    • ループから出てきます

• 一致がゼロ以外の場合、-

  • minLen：=len

  • minab：=マスク

• それ以外の場合-

  • 初期化b：=ビットの場合、b を実行します。

    • （cand AND b）が0に等しくない場合、-

      • dfs（b * 2、マスクOR b）

• メインの方法から、次のようにします-

• ret：=空白の文字列

• n：=ターゲットのサイズ

• bn：=2 ^ n

• cand：=0

• minLen：=inf

• 辞書の各sについて-

  • sのサイズがnと等しくない場合、-

    • 次の部分を無視し、次の反復にスキップします

  • 単語：=0

  • 初期化i：=0の場合、i

    • s[i]がtarget[i]と等しくない場合、-

      • 単語：=単語OR（2 ^ i）

  • dictの最後に単語を挿入

  • cand：=cand OR word

• dfs（1、0）

• 初期化i：=0の場合、i

  • （minab AND 2 ^ i）が0に等しくない場合、-

    • ret：=ret + target [i]

    • （iを1増やします）

  • それ以外の場合

    • j：=i

    • （i

      • （iを1増やします）

    • ret：=ret concatenate（i --j）

• 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