Add Bold Tag in String – เพิ่มแท็ก Bold ในสตริง C++

ปัญหา: Add Bold Tag in String

กำหนดสตริง s และพจนานุกรม dict ใส่แท็ก <b> และ </b> ครอบ ทุก substring ใน s ที่อยู่ใน dict
- Substring ทับซ้อน → รวมเป็นแท็กเดียว
- Substring ติดกัน → รวมเป็นแท็กเดียว

ตัวอย่าง

s = "abcxyz123", dict = ["abc", "123"]
Output: "<b>abc</b>xyz<b>123</b>"

แนวทางแก้ปัญหา: Boolean Array + Merge Intervals

ขั้นตอน

1. สร้าง bold[n] (n = s.length) – bold[i] = true ถ้าตำแหน่ง i อยู่ใน substring ที่ต้อง bold
2. สแกน s ทุกตำแหน่ง i:
   • ตรวจสอบทุกคำใน dict ว่า match ที่ i ไหม
   • ถ้า match → end = max(end, i + word.length())
3. bold[i] = (end > i)
4. สร้างผลลัพธ์: วน i ตาม bold array
   • ถ้า bold[i] เริ่มช่วง → ใส่ <b>
   • เพิ่มตัวอักษร
   • ถ้า bold[i] จบช่วง → ใส่ </b>

ตัวอย่างโค้ด C++

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

class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        int n = s.size();
        vector<bool> bold(n, false);

        // Mark bold regions
        for (int i = 0, end = 0; i < n; i++) {
            for (const string& word : dict) {
                if (s.substr(i, word.size()) == word)
                    end = max(end, i + (int)word.size());
            }
            bold[i] = (end > i);
        }

        // Build result
        string res;
        for (int i = 0; i < n; ) {
            if (!bold[i]) {
                res += s[i++];
            } else {
                res += "";
                int j = i;
                while (j < n && bold[j]) res += s[j++];
                res += "";
                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 = |s|, m = |dict|, k = ความยาวคำเฉลี่ย
• พื้นที่: O(n) – bold array

การเพิ่มประสิทธิภาพ (Trie + Aho-Corasick)

ถ้า dict ใหญ่ → ใช้ Trie หา substring ทั้งหมดใน O(n + total_dict_len + matches)

ข้อสังเกต

• LeetCode 616 (Add Bold Tag in String)
• Boolean array approach เรียบง่าย สำหรับ dict เล็ก-ปานกลาง
• จัดการ overlapping และ consecutive intervals อัตโนมัติด้วย bold array
• โค้ดต้นฉบับมี logic ซับซ้อนในการ build string – วิธีนี้ชัดเจนกว่า