616. Add Bold Tag in String

Problem

Bạn được cho một chuỗi s và một mảng các từ words. Nhiệm vụ là thêm cặp tag  và  để bọc các đoạn con của s xuất hiện trong words. Nếu các đoạn cần bôi đen bị chồng lắp hoặc liền kề nhau, bạn cần gộp chúng lại thành một cặp tag duy nhất

Ví dụ

Input: s = "abcxyz123", words = ["abc","123"]

Output: "abcxyz123"

Approach

Đánh dấu vị trí cần bôi đen:

Khởi tạo một mảng boolean isBold có độ dài bằng s, tất cả giá trị ban đầu là false.

Với mỗi từ trong words, tìm tất cả các vị trí xuất hiện trong s, và đánh dấu các vị trí tương ứng trong isBold thành true4 3 5.

Tạo kết quả với tag :

Duyệt chuỗi s và sử dụng isBold để xác định vị trí cần mở/đóng tag .

Khi chuyển từ false sang true (hoặc là ký tự đầu tiên cần bôi đen), thêm .

Khi chuyển từ true sang false (hoặc là ký tự cuối cùng cần bôi đen), thêm .

Ưu điểm

Đơn giản, dễ hiểu, dễ cài đặt.

Đảm bảo đúng yêu cầu gộp các đoạn chồng lắp hoặc liền kề.

Time and space complexity

TC: O(m * n * k)

Với mỗi từ trong words (duyệt m lần), bạn kiểm tra tất cả các vị trí bắt đầu hợp lệ trong s (tối đa n lần cho mỗi từ), và so sánh chuỗi con độ dài k.

Thao tác so sánh chuỗi con mất O(k) cho mỗi lần kiểm tra.

SC: O(m * n * k + n)

Solution

javascriptjavascript

1function addBoldTag(s: string, words: string[]): string {
2    const n = s.length;
3    const is_bold: boolean[] = Array(n).fill(false);
4    for (const word of words) {
5        let start = 0;
6        while (start <= n - word.length) {
7            if (s.substring(start, start + word.length) === word) {
8                for (let i = start; i < start + word.length; i++) is_bold[i] = true;
9            }
10            start++
11        }
12    }
13
14    let res = '';
15    let i = 0
16    while (i < n) {
17        if (is_bold[i] && (i === 0 || !is_bold[i - 1])) {
18            res += '<b>';
19        }
20
21        res += s[i];
22        if (is_bold[i] && (i === n - 1 || !is_bold[i + 1])) {
23            res += '</b>'
24        }
25        i++
26    }
27    return res
28};

💡

i === n - 1: Nếu là ký tự cuối cùng, chắc chắn phải đóng tag nếu nó đang bôi đen

!is_bold[i + 1] Nếu ký tự tiếp theo không bôi đen, tức là kết thúc đoạn bôi đen hiện tại, phải đóng tag

Loading content...

1function addBoldTag(s: string, words: string[]): string { 2 const n = s.length; 3 const is_bold: boolean[] = Array(n).fill(false); 4 for (const word of words) { 5 let start = 0; 6 while (start <= n - word.length) { 7 if (s.substring(start, start + word.length) === word) { 8 for (let i = start; i < start + word.length; i++) is_bold[i] = true; 9 } 10 start++ 11 } 12 } 13 14 let res = ''; 15 let i = 0 16 while (i < n) { 17 if (is_bold[i] && (i === 0 || !is_bold[i - 1])) { 18 res += ''; 19 } 20 21 res += s[i]; 22 if (is_bold[i] && (i === n - 1 || !is_bold[i + 1])) { 23 res += '' 24 } 25 i++ 26 } 27 return res 28};