The Algorithm to Make Words Bold in HTML

  • 时间:2020-09-24 11:41:27
  • 分类:网络文摘
  • 阅读:93 次

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between and tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = [“ab”, “bc”] and S = “aabcd”, we should return “aabcd”. Note that returning “aabcd” would use more tags, so it is incorrect.

Note:

  • words has length in range [0, 50].
  • words[i] has length in range [1, 10].
  • S has length in range [0, 500].
  • All characters in words[i] and S are lowercase letters.

Make String Bold using Bruteforce Algorithm

Without the requirement of the shortest, we can make bold on every occurrences of the words in the list. As we are given the original HTML string, we can mark bold for each character that appears in the bold words.

So, with O(N) space, and O(NM) where N is the size of the string and M is the total length of the bold string, the following C++ bruteforce algorithm will insert the least HTML bold tags that satisfy the requirement.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string boldWords(vector<string>& words, string S) {
        int n = S.size();
        vector<bool> bold(n, false);
        for (const auto &s: words) {
            for (int i = 0; i + s.size() - 1 < n; ++ i) {
                bool ok = true;
                for (int k = 0; k < s.size(); ++ k) {
                    if (s[k] != S[i + k]) { // bold string s not found in the string
                        ok = false;
                        break;
                    }
                }
                if (ok) { // it is bold
                    for (int k = 0; k < s.size(); ++ k) {
                        bold[i + k] = true; // mark the character bold
                    }
                }
            }
        }
        string ans = "";
        for (int i = 0; i < n; ++ i) {
            // bold start boundary
            if (bold[i] && (i == 0 || !bold[i - 1])) ans += "<b>"; 
            ans += S[i];
            // bold end boundary
            if (bold[i] && (i == n - 1 || !bold[i + 1])) ans += "</b>";
        }
        return ans;
    }
};
class Solution {
public:
    string boldWords(vector<string>& words, string S) {
        int n = S.size();
        vector<bool> bold(n, false);
        for (const auto &s: words) {
            for (int i = 0; i + s.size() - 1 < n; ++ i) {
                bool ok = true;
                for (int k = 0; k < s.size(); ++ k) {
                    if (s[k] != S[i + k]) { // bold string s not found in the string
                        ok = false;
                        break;
                    }
                }
                if (ok) { // it is bold
                    for (int k = 0; k < s.size(); ++ k) {
                        bold[i + k] = true; // mark the character bold
                    }
                }
            }
        }
        string ans = "";
        for (int i = 0; i < n; ++ i) {
            // bold start boundary
            if (bold[i] && (i == 0 || !bold[i - 1])) ans += "<b>"; 
            ans += S[i];
            // bold end boundary
            if (bold[i] && (i == n - 1 || !bold[i + 1])) ans += "</b>";
        }
        return ans;
    }
};

After the bold characters are marked, we re-scan the string and look for the boundarys, and insert the tags accordingly.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
Algorithms to Shift a 2D Grid/Matrix In-Place  How Martha Stewart Became One Of The Best Bloggers On The Web  Social Media and Dating Apps: How They’re Changing Love  Did You Know There Are Some Great Scientific Reasons to Use Emot  5 Simple Tips for Creating More Irresistible Product Pages  You Should Know These Facts About Instagram  Why Bloggers Need to Understand Google Rankbrain  How to Write Compelling Blog Content for Boring Niches  Why Curvy Blogger Put On A Bikini For The First Time In 25 Years  Blogger Gives His Secret To Becoming A Millionaire By Age 30 
评论列表
添加评论