C++-এ ন্যূনতম unik Word Abbreviation (Minimum Unique Word Abbreviation)

ধরি আমাদের একটি স্ট্রিং আছে যেমন "word" এবং এর নিচের সংক্ষিপ্ত রূপ (abbreviations) থাকতে পারে: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]। আমাদের একটি টার্গেট স্ট্রিং এবং একটি ডিকশনারি (শব্দকোষ) দেওয়া আছে। আমাদের টার্গেট স্ট্রিংর এমন একটি সংক্ষিপ্ত রূপ বের করতে হবে যেটার দৈর্ঘ্য সর্বনিম্ন এবং ডিকশনারির শব্দগুলোর সংক্ষিপ্ত রূপের সাথে কনফ্লিক্ট (conflict) করে না। এখানে সংক্ষিপ্ত রূপে প্রতিটি সংখ্যা বা অক্ষর দৈর্ঘ্য 1 হিসেবে গুন হবে। উদাহরণস্বরূপ, "a32bc" দৈর্ঘ্য 4।

উদাহরণস্বরূপ, ইনপুট "apple", ডিকশনারি = ["blade"] হলে আউটপুট হবে "a4"।

সমাধানের ধাপসমূহ

• একটি অ্যারে dict সংজ্ঞায়িত।
• abbrLen() ফাংশন সংজ্ঞায়িত: এটি mask নিবে।
  • ret := n
  • b = 3 থেকে bn পর্যন্ত b <<= 1:
    • যদি (mask & b) == 0: ret--
  • ret ফেরত।
• dfs() ফাংশন সংজ্ঞায়িত: এটি bit, mask নিবে।
  • len := abbrLen(mask)
  • যদি len >= minLen: ফেরত।
  • match := true
  • dict-র প্রতিটি d জন্য:
    • যদি (mask & d) == 0: match = false; ব্রেক।
  • যদি match: minLen = len; minab = mask
  • অন্যথায়:
    • b = bit থেকে bn পর্যন্ত b <<= 1:
      • যদি (cand & b) != 0: dfs(b<<1, mask | b)
• মেইন মেথড থেকে:
  • ret := খালি স্ট্রিং
  • n := target.size()
  • bn := 1 << n
  • cand := 0, minLen := INF
  • ডিকশনারির প্রতিটি s জন্য:
    • যদি s.size() != n: continue
    • word := 0
    • i = 0 থেকে s.size()-1: যদি s[i] != target[i]: word |= (1 << i)
    • dict-এ word পুশ, cand |= word
  • dfs(1, 0)
  • i = 0 থেকে n-1 পর্যন্ত:
    • যদি (minab & (1<
    • অন্যথায়: j := i; যখন i < n এবং (minab & (1<
  • ret ফেরত।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int n, cand, bn, minLen, minab;
    vector 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& 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;
    }
};

int main() {
    Solution ob;
    vector v = {"blade"};
    cout << (ob.minAbbreviation("apple", v));
}

ইনপুট

"apple", {"blade"}

আউটপুট

a4