मान लीजिए हमारे पास एक स्ट्रिंग s और स्ट्रिंग्स की एक सूची dict है, हमें s में उन उपस्ट्रिंग्स को लपेटने के लिए बोल्ड टैग और का एक बंद युग्म जोड़ना होगा जो dict में मौजूद हैं। जब दो ऐसी उपस्ट्रिंग्स ओवरलैप होती हैं, तो हमें उन्हें केवल एक युग्म बोल्ड टैग से एक साथ लपेटना होगा। इसके अलावा, यदि बोल्ड टैग से लिपटी दो उपस्ट्रिंग्स लगातार हैं, तो हमें उन्हें संयोजित करना होगा।
उदाहरण के लिए, यदि इनपुट s = "abcxyz123" है और dict = ["abc","123"] है, तो आउटपुट "abcxyz123" होगा।
हल करने की विधि
हम एक बोलियन सरणी का उपयोग करके बोल्ड क्षेत्रों को चिह्नित करेंगे:
- n = s का आकार।
- आकार n की बोलियन सरणी bold परिभाषित करें।
- प्रत्येक इंडेक्स i के लिए, dict में प्रत्येक शब्द की जांच करें कि क्या यह i से शुरू होता है, यदि हां, तो अंत इंडेक्स को अपडेट करें।
- bold[i] = end > i सेट करें।
- फिर स्ट्रिंग को पार करें: यदि bold[i] गलत है, तो वर्ण जोड़ें; यदि सही है, तो लगातार बोल्ड क्षेत्र ढूंढें, टैग के साथ लपेटें।
- परिणाम स्ट्रिंग लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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); string ret = ""; for (int i = 0, end = 0; i < s.size(); i++) { for (int j = 0; j < dict.size(); j++) { if (s.substr(i, dict[j].size()) == dict[j]) { end = max(end, i + (int)dict[j].size()); } } bold[i] = end > i; } int j; for (int i = 0; i < s.size(); i = j) { if (!bold[i]) { ret += s[i]; j = i + 1; continue; } j = i; while (j < s.size() && bold[j]) j++; ret += "<b>" + s.substr(i, j - i) + "</b>"; } return ret; } }; main(){ Solution ob; vector<string> v = {"abc","123"}; cout << (ob.addBoldTag("abcxyz123", v)); }
इनपुट
"abcxyz123", ["abc","123"]
आउटपुट
<b>abc</b>xyz<b>123</b>