Bold Words in String LeetCode Solution

Difficulty Level Medium
Frequently asked in GoogleViews 2195

Problem Statement

Bold Words in String LeetCode Solution – Given an array of keywords words and a string s, make all appearances of all keywords words[i] in s bold. Any letters between <b> and </b> tags become bold.

Return s after adding the bold tags. The returned string should use the least number of tags possible, and the tags should form a valid combination.Bold Words in String LeetCode Solution

Example

Test Case 1:

Input:

words = [“ab”, “bc”]

s = “aabcd”

Output:

“a<b>ab</b>cd”

Explanation

We might think returning “a<b>a<b>b</b>c</b>d” will be easy. But it would use more tags. But we need to use the least number of tags. So the correct output is “a<b>ab</b>cd”.

Approach

Idea

  1. boldMap initialize with all 0, use for mark bold char.
  2. Go through each word and mark it in boldMap.
  3. loop through string S and use openTag to check if we should open or close the tag.
  4. In the end, if the tag is still open, we should close it.

Code for Bold Words in String LeetCode Solution

Java Program

class Solution {
    public String boldWords(String[] words, String s) {
        boolean[] bold = new boolean[s.length() + 1];
        for(String w : words)
            for(int i = s.indexOf(w); i != -1; i = s.indexOf(w, i + 1))
                Arrays.fill(bold, i, i + w.length(), true);
        StringBuilder r = new StringBuilder(bold[0] ? "<b>" : "");
        for(int i = 0; i < bold.length - 1; i++){
            r.append(s.charAt(i));
            r.append(bold[i] && !bold[i + 1] ? "</b>" : "");
            r.append(!bold[i] && bold[i + 1] ? "<b>" : "");
        }
        return r.toString();
    }
}

C++ Program

class Solution {
public:
    string boldWords(vector<string>& words, string S) {
        vector<bool> bold(S.size(), false);
        for(int i=0;i<words.size();i++) {
            for(int j=0;j+words[i].size()<=S.size();j++) {
                if(S.substr(j, words[i].size())!=words[i]) continue;
                for(int k=0;k<words[i].size();k++) bold[j+k]=true;
            }
        }
        string res;
        if(bold[0]) res+="<b>";
        for(int i=0;i<S.size();i++) {
            res.append(1, S[i]);
            if(i==S.size()-1) break;
            if(!bold[i]&&bold[i+1]) res+="<b>";
            else if(bold[i]&&!bold[i+1]) res+="</b>";
        }
        if(bold.back()) res+="</b>";
        return res;
    }
};

Complexity Analysis for Bold Words in String LeetCode Solution

Let N be the length of the input string.

Time complexity: O(N)

We are only iterating over the input string. So it will take O(N) time.

Space complexity: O(N)

We are storing the string in an array. So it will take O(N) space.

Reference: https://en.wikipedia.org/wiki/Wikipedia:Manual_of_Style/Text_formatting

Translate »