Thêm thẻ in đậm vào chuỗi trong C++

Giới thiệu

Cho chuỗi s và từ điển dict (danh sách chuỗi). Bọc tất cả các chuỗi con của s xuất hiện trong dict bằng thẻ <b> và </b>. Nếu các đoạn bọc chồng lấn hoặc liền kề, gộp thành một cặp thẻ duy nhất.

Thuật toán: Mảng đánh dấu + Ghép đoạn

1. Tạo mảng bold[n] (n = độ dài s), khởi tạo false.
2. Với mỗi vị trí i, kiểm tra mọi từ trong dict: nếu s.substr(i, len) == word → đánh dấu bold[i..i+len-1] = true (cập nhật end = max(end, i+len)).
3. Duyệt chuỗi xây kết quả: nếu bold[i] false → thêm ký tự. Nếu true → tìm đoạn liên tiếp true, bọc <b>...</b>.

Cài đặt C++

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

class Solution {
public:
    string addBoldTag(string s, vector& dict) {
        int n = s.size();
        vector 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++]; continue; }
            int j = i;
            while (j < n && bold[j]) j++;
            res += "" + s.substr(i, j - i) + "";
            i = j;
        }
        return res;
    }
};

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

Phân tích

• Thời gian: O(n * m * L) với n=|s|, m=|dict|, L=độ dài từ trung bình. Có thể tối ưu bằng Trie/AC automaton.
• Không gian: O(n).

LeetCode 616 "Add Bold Tag in String".