เพิ่มแท็กตัวหนาในสตริงใน C ++

สมมติว่าเรามีสตริง s และรายการสตริงที่เรียกว่า dict เราต้องเพิ่มแท็กตัวหนา และ ปิดเพื่อตัดสตริงย่อยใน s ที่มีอยู่ใน dict นั้น เมื่อสตริงย่อยดังกล่าวทับซ้อนกัน เราต้องรวมเข้าด้วยกันด้วยแท็กตัวหนาที่ปิดเพียงคู่เดียว นอกจากนี้ หากสตริงย่อยสองสตริงที่แท็กตัวหนาอยู่ติดกัน เราจำเป็นต้องรวมเข้าด้วยกัน

ดังนั้น หากอินพุตเป็น s ="abcxyz123" dict คือ ["abc","123"] เอาต์พุตจะเป็น "abcxyz123" พี>

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ s

• กำหนดขนาดตัวหนาของอาร์เรย์ n

• ret :=สตริงว่าง

• สำหรับการเริ่มต้น i :=0, end :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของ dict ให้อัปเดต (เพิ่ม j ขึ้น 1) ทำ -

    • ถ้าสตริงย่อยของ s จากดัชนี (i ถึงขนาดของ dict[j] - 1) เหมือนกับ dict[j] ดังนั้น −

      • end :=สูงสุดของ end และ i + ขนาดของ dict[j]

  • ตัวหนา[i] :=end> i

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของ s ให้อัปเดต i =j ทำ −

  • ถ้าตัวหนา[i] เป็นศูนย์ ดังนั้น −

    • ret :=ret + s[i]

    • เจ :=ผม + 1

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • เจ :=ฉัน

  • ในขณะที่ (j <ขนาดของ s และตัวหนา[j] ไม่ใช่ศูนย์) ทำ −

    • (เพิ่มขึ้น j โดย 1)

  • ret :=สตริงย่อยของ ret จากดัชนี i ถึง j - i - 1 เชื่อม "" ต่อกัน s

• รีเทิร์น

#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>