05 August 2008
一个字符串 s 和一个字符串单词数组。应该添加一对封闭的粗体标记 和 以将子字符串包装在单词中存在的 s 中。如果两个这样的子字符串重叠，您应该只用一对封闭的粗体标签将它们包装在一起。如果用粗体标签包裹的两个子字符串是连续的，则应将它们组合起来。
添加粗体标签后返回 s。
Example 1:
1
2
Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
Example 2:
1
2
Input: s = "aaabbcc", words = ["aaa","aab","bc"]
Output: "<b>aaabbc</b>c"
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
class Solution {
/*
Use a boolean array to mark if character at each position is bold or not.
*/
public String addBoldTag(String s, String[] dict) {
boolean[] bold = new boolean[s.length()]; //boolean array标记每个character
for (int i = 0, end = 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;
}
StringBuilder result = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!bold[i]) {
result.append(s.charAt(i));
continue;
}
int j = i;
while (j < s.length() && bold[j]) {
j++;
}
result.append("<b>").append(s.substring(i, j)).append("</b>");
i = j - 1;
}
return result.toString();
}
}