স্ট্রিংয়ে বোল্ড ট্যাগ যোগ করা C++-এ

সমস্যা বিবরণ

একটি স্ট্রিং s এবং ডিকশনারি dict (স্ট্রিং লিস্ট) দেওয়া আছে। s-এ dict-এর স্ট্রিংগুলো খুঁজে সেগুলো <b> ও </b> ট্যাগ দিয়ে বোল্ড করুন। ওভারল্যাপ বা কনsekutিভ সাবস্ট্রিং হলে একই ট্যাগ দিয়ে মёрজ করুন।

উদাহরণ

s = "abcxyz123", dict = ["abc","123"]

আউটপুট: "abcxyz123"

অ্যালগরিদম: বোল্ড মার্কার অ্যারে

1. bold[i] = true যদি i-তম ক্যারেক্টার বোল্ড হওয়া উচিত।
2. প্রতিটি ইন্ডেক্স i থেকে সব ডিকশনারি ওয়ার্ড ম্যাচ করান। ম্যাচ হলে end = max(end, i + len) আপডেট করুন।
3. bold[i] = (end > i)।
4. এবার স্ট্রিং ট্রাভার্স করে:
   • bold[i] == false হলে ক্যারেক্টার যোগ করুন।
   • bold[i] == true হলে <b> খুলুন,련속 true থাকা পর্যন্ত ক্যারেক্টার যোগ করুন, পরে </b> বন্ধ করুন।

C++ বাস্তবায়ন

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

class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        int n = s.size();
        vector<int> bold(n, 0);
        for (int i = 0, end = 0; i < n; i++) {
            for (auto& w : dict) {
                if (s.substr(i, w.size()) == w)
                    end = max(end, i + (int)w.size());
            }
            bold[i] = end > i;
        }

        string res;
        for (int i = 0; i < n; ) {
            if (!bold[i]) {
                res += s[i++];
            } else {
                int j = i;
                while (j < n && bold[j]) j++;
                res += "" + s.substr(i, j - i) + "";
                i = j;
            }
        }
        return res;
    }
};

int main() {
    Solution ob;
    vector<string> dict = {"abc", "123"};
    cout << ob.addBoldTag("abcxyz123", dict); // abcxyz123
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n × m × k) — n = স্ট্রিং লেন্থ, m = ডিকশনারি সাইজ, k = গড় ওয়ার্ড লেন্থ।
• স্থান জটিলতা: O(n) — বোল্ড অ্যারে।