Formatted question description: https://leetcode.ca/all/758.html
758. Bold Words in String
Level
Easy
Description
Given a set of keywords words
and a string S
, make all appearances of all keywords in S
bold. Any letters between <b>
and </b>
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 "a<b>abc</b>d"
. Note that returning "a<b>a<b>b</b>c</b>d"
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]
andS
are lowercase letters.
Solution
Use an array with type boolean
to determine whether each index should become bold. Find indices of all occurrences of keywords in S
, and set all the indices where the keywords occur to be bold.
Loop over the string S
, and add tags at start and end indices in S
.
class Solution {
public String boldWords(String[] words, String S) {
int length = S.length();
boolean[] bold = new boolean[length];
for (String word : words) {
int wordLength = word.length();
int beginIndex = 0;
while (beginIndex >= 0) {
beginIndex = S.indexOf(word, beginIndex);
if (beginIndex >= 0) {
for (int i = 0; i < wordLength; i++)
bold[beginIndex + i] = true;
beginIndex++;
}
}
}
StringBuffer sb = new StringBuffer(S);
if (bold[length - 1])
sb.append("</b>");
for (int i = length - 1; i > 0; i--) {
if (bold[i] && !bold[i - 1])
sb.insert(i, "<b>");
else if (!bold[i] && bold[i - 1])
sb.insert(i, "</b>");
}
if (bold[0])
sb.insert(0, "<b>");
String boldStr = sb.toString();
return boldStr;
}
}