-
Notifications
You must be signed in to change notification settings - Fork 8
/
BoldWordsInString.java
82 lines (76 loc) · 2.49 KB
/
BoldWordsInString.java
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package stringmatch;
// Source : https://leetcode.com/problems/bold-words-in-string/
// Id : 758
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Date : 2020-01-12
// Topic : String Match
// Level : Easy +
// Other : Same with 616
// Tips :
// Result : 96.18% 100.00%
public class BoldWordsInString {
// 7.63% 65 ms 100.00%
public String boldWords(String[] words, String S) {
boolean[] boldCharIndex = new boolean[S.length()];
for (String word : words) {
for (int i = 0; i < S.length() - word.length() + 1; i++) {
boolean match = true;
for (int j = 0; j < word.length(); j++) {
if (word.charAt(j) != S.charAt(i + j)) {
match = false;
break;
}
}
if (match) {
for (int j = 0; j < word.length(); j++)
boldCharIndex[i + j] = true;
match = false;
}
}
}
return getBoldWords(S, boldCharIndex);
}
private String getBoldWords(String s, boolean[] boldCharIndex) {
StringBuilder stringBuilder = new StringBuilder();
boolean started = false;
for (int i = 0; i < s.length(); i++) {
if (started) {
if (boldCharIndex[i] != true) {
stringBuilder.append("</b>");
started = false;
}
stringBuilder.append(s.charAt(i));
} else {
if (boldCharIndex[i] == true) {
stringBuilder.append("<b>");
started = true;
}
stringBuilder.append(s.charAt(i));
}
}
if (started)
stringBuilder.append("</b>");
return stringBuilder.toString();
}
/**
* used String.index which is more efficient
*
* @param words
* @param S
* @return
*/
// 96.18% 6ms
public String boldWords1(String[] words, String S) {
// public String boldWords(String[] words, String S) {
boolean[] isBold = new boolean[S.length()];
for (String word : words) {
int n = S.indexOf(word, 0);
while (n != -1) {
for (int i = n; i < n + word.length(); i++)
isBold[i] = true;
n = S.indexOf(word, n + 1);
}
}
return getBoldWords(S, isBold);
}
}