版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434636
Problem:
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:
思路:
S的长度不长,所以可以用一个boolean数组记录每个位置是否需要加粗。起初,我for循环两次S,得到可能的subString判断是否在words中存在,结果超时了,解决超时的关键在于note,words的长度最多就10,所以干脆从可能的word中找是否有对应S的subString,这样即解决了超时。
Java版本如下:
public String boldWords(String[] words, String S) {
int n = S.length();
boolean[] marked = new boolean[n];
for (int i = 0; i < n; ++i) {
for (String word : words) {
if (i + word.length() <= n && word.equals(S.substring(i, i + word.length()))) {
for (int j = i; j < i + word.length(); ++j) {
marked[j] = true;
}
}
}
}
StringBuilder sb = new StringBuilder();
int j = 0;
while (j < n) {
while (j < n && !marked[j]) {
sb.append(S.charAt(j));
j ++;
}
if (j >= n) break;
StringBuilder tmp = new StringBuilder();
while (j < n && marked[j]) {
tmp.append(S.charAt(j));
j ++;
}
if (tmp.length() != 0) sb.append("<b>" + tmp.toString() + "</b>");
}
return sb.toString();
}
不过我们还可以采用IMOS累积法,这样可以省去一个for循环。
Java代码如下:
public String boldWords(String[] words, String S) {
int n = S.length();
int[] hits = new int[n];
for (int i = 0; i < n; ++i) {
for (String word : words) {
if (i + word.length() <= n && word.equals(S.substring(i, i + word.length()))) {
hits[i] ++;
hits[i + word.length()] --;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i < n; ++i) hits[i] += hits[i - 1];
for (int i = 0; i < n; ++i) {
if (hits[i] > 0) {
sb.append("<b>" + S.charAt(i) + "</b>");
}
else sb.append(S.charAt(i));
}
return sb.toString().replace("</b><b>", "");
}
Python版本:
class Solution(object):
def boldWords(self, words, S):
"""
:type words: List[str]
:type S: str
:rtype: str
"""
n = len(S)
hits = [0] * (n + 1)
for i in range(n):
for word in words:
if (i + len(word) <= n and word == S[i:i + len(word)]):
hits[i] += 1
hits[i + len(word)] -= 1
for i in range(1, n + 1): hits[i] += hits[i - 1]
ans = ""
i = 0;
while (i < n):
while (i < n and hits[i] == 0):
ans += S[i]
i += 1
if i >= n: break
tmp = ""
while (i < n and hits[i] != 0):
tmp += S[i]
i += 1
if (len(tmp) != 0): ans += "<b>" + tmp + "</b>"
return ans