C++-এ শর্ট এনকোডিং অফ ওয়ার্ডস সমস্যা সমাধান

মান করুন আমাদের একটি ওয়ার্ড লিস্ট দেওয়া আছে, আমরা এটিকে একটি রেফারেন্স স্ট্রিং S এবং একটি ইনডেক্স লিস্ট A লিখে এনকোড করতে পারি। উদাহরণস্বরূপ, যদি ওয়ার্ড লিস্ট হয় ["time", "me", "bell"], তবে আমরা এটিকে S = "time#bell#" এবং ইনডেক্স = [0, 2, 5] হিসেবে লিখতে পারি। এখানে প্রতিটি ইনডেক্সের জন্য, আমরা রেফারেন্স স্ট্রিং থেকে সেই ইনডেক্স থেকে পড়া শুরু করব "#" চিহ্ন পাওয়ার পর্যন্ত।

আমাদের বের করতে হবে দেওয়া ওয়ার্ডগুলো এনকোড করার জন্য সবচেয়ে ছোট রেফারেন্স স্ট্রিং S-এর দৈর্ঘ্য কত? দেওয়া উদাহরণের জন্য আউটপুট হবে ১০।

এটি সমাধান করার জন্য নিচের ধাপগুলি অনুসরণ করুন −

insertNode মেথড সংজ্ঞায়িত করুন, এটি head এবং স্ট্রিং s নেবে
curr := head, flag := false
i = s.size() - 1 থেকে 0 পর্যন্ত
- x := s[i]
- যদি curr->m[x] null হয়, তবে flag := true সেট করুন এবং একটি নতুন নোড তৈরি করুন curr->m[x]-এ
- curr := curr->m[x]
flag true হলে s.size() ফেরত দিন, অন্যথায় 0
মেইন মেথড থেকে নিচের কাজ করুন −
- ret := 0, head := new node
- words অ্যারে দৈর্ঘ্য অনুযায়ী সর্ট করুন
- n := words-এর আকার
- i = 0 থেকে n - 1 পর্যন্ত
  - temp := insertNode(head, words[i])
  - যদি temp নন-জিরো হয়, তবে ret := ret + temp + 1
- ret ফেরত দিন

উদাহরণ কোড

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

struct Node{
    map <char, Node*> m;
};

class Solution {
public:
    static bool cmp(string a, string b){
        return a.size() > b.size();
    }
    
    int insertNode(Node* head, string s){
        Node* curr = head;
        bool flag = false;
        for(int i = s.size() - 1; i >= 0; i--){
            char x = s[i];
            if(!curr->m[x]){
                flag = true;
                curr->m[x] = new Node();
            }
            curr = curr->m[x];
        }
        return flag ? (int)s.size() : 0;
    }
    
    int minimumLengthEncoding(vector<string>& words) {
        int ret = 0;
        Node* head = new Node();
        sort(words.begin(), words.end(), cmp);
        int n = words.size();
        for(int i = 0; i < n; i++){
            int temp = insertNode(head, words[i]);
            if(temp){
                ret += (temp + 1);
            }
        }
        return ret;
    }
};

main(){
    vector<string> v = {"time", "me", "bell"};
    Solution ob;
    cout << (ob.minimumLengthEncoding(v));
}

ইনপুট

["time", "me", "bell"]