Add Bold String

XXX.Add Bold Tag in String

String

Simulation

Problem Statement:

Given a string s and a list of words in a dictionary dict, add a bold tag <b> and </b> around substrings in s that exist in dict. If multiple substrings overlap, they should be wrapped in a single bold tag.

Algorithm:

1. Initialize a boolean array to mark positions in the string that should be bold.
2. For each character in the string, check if any word in the dictionary starts from that position.
3. Update the bold array to mark the range of characters that belong to bold substrings.
4. Iterate through the string and construct the result:
   • Wrap substrings marked as bold with <b> and </b>.
   • Append non-bold characters directly to the result.

Complexity:

Time: O(n * m + n), where n is the length of the string and m is the total length of all dictionary words. | Space: O(n) for the bold array and result construction.

Java Implementation:

public class Solution {
    public String addBoldTag(String s, String[] dict) {
        boolean[] bold = new boolean[s.length()];
        int end = 0;

        // Mark bold positions in the string
        for (int i = 0; i < s.length(); i++) {
            for (String word : dict) 
                if (s.startsWith(word, i)) 
                    end = Math.max(end, i + word.length());
            bold[i] = end > i; // Mark if this position is within a bold range
        }

        StringBuilder result = new StringBuilder();
        int i = 0;

        // Construct the result with bold tags
        while (i < s.length()) {
            if (!bold[i]) {
                result.append(s.charAt(i++)); // Append non-bold characters
                continue;
            }
            int j = i;
            while (j < s.length() && bold[j]) j++;
            result.append("").append(s.substring(i, j)).append("");
            i = j;
        }

        return result.toString();
    }
}
                

Python Implementation:

def addBoldTag(s, words):
    bold = [False] * len(s)
    end = 0

    # Mark bold positions in the string
    for i in range(len(s)):
        for word in words:
            if s.startswith(word, i):
                end = max(end, i + len(word))
        bold[i] = end > i

    result = []
    i = 0

    # Construct the result with bold tags
    while i < len(s):
        if not bold[i]:
            result.append(s[i])
            i += 1
            continue
        j = i
        while j < len(s) and bold[j]:
            j += 1
        result.append("" + s[i:j] + "")
        i = j

    return "".join(result)
                

C++ Implementation:

string addBoldTag(string s, vector& words) {
    vector bold(s.length(), false);
    int end = 0;

    // Mark bold positions in the string
    for (int i = 0; i < s.length(); i++) {
        for (const string& word : words) {
            if (s.compare(i, word.length(), word) == 0) 
                end = max(end, i + (int)word.length());
        }
        bold[i] = end > i;
    }

    string result;
    int i = 0;

    // Construct the result with bold tags
    while (i < s.length()) {
        if (!bold[i]) {
            result += s[i++];
            continue;
        }
        int j = i;
        while (j < s.length() && bold[j]) j++;
        result += "" + s.substr(i, j - i) + "";
        i = j;
    }

    return result;
}