Bold Words in String - CPP Solution

1. Introduction

In this blog post, we'll explore a unique string processing problem in C++ known as "Bold Words in String". This problem involves formatting a given string by bolding specific substrings. It's a great example of string manipulation, highlighting the use of algorithms to process and modify strings based on certain criteria.

Problem

Given a string s and an array of words words, the task is to add HTML bold tags around the substrings in s that appear in words. The goal is to use the minimum number of tags to cover all occurrences of the words.

2. Solution Steps

1. Create a boolean array bold to mark the characters in s that should be bold.

2. Iterate over s and mark the ranges that contain words from words.

3. Build the resulting string:

- Add a <b> tag before a sequence of bold characters.

- Copy the characters from s.

- Add a </b> tag after the sequence.

4. Return the formatted string.

3. Code Program

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Function to add HTML bold tags around words in 's' that appear in 'words'
string addBoldTag(string s, vector<string>& words) {
    vector<bool> bold(s.length(), false);

    // Mark the bold characters
    for (const auto& word : words) {
        size_t pos = s.find(word);
        while (pos != string::npos) {
            fill(bold.begin() + pos, bold.begin() + pos + word.length(), true);
            pos = s.find(word, pos + 1);
        }
    }

    // Build the result string with bold tags
    string result;
    for (size_t i = 0; i < s.length(); i++) {
        if (bold[i] && (i == 0 || !bold[i - 1])) {
            result += "<b>";
        }
        result += s[i];
        if (bold[i] && (i == s.length() - 1 || !bold[i + 1])) {
            result += "</b>";
        }
    }
    return result;
}

int main() {
    string s = "abcxyz123";
    vector<string> words = {"abc","123"};
    cout << "Formatted string: " << addBoldTag(s, words) << endl;
    return 0;
}

Output:

Formatted string: abcxyz123

Explanation:

1. The input string "abcxyz123" and words ["abc","123"] are processed.

2. Characters in 's' that match the words are marked to be bolded.

3. The function then iterates through 's', adding <b> tags before and </b> tags after the bold sequences.

4. The output "<b>abc</b>xyz<b>123</b>" correctly formats the string, with the specified words in bold.

5. This approach efficiently adds bold formatting to specified words in a string, demonstrating practical string manipulation in C++.