Welcome to Subscribe On Youtube
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; } }
-
Todo
-
class Trie: def __init__(self): self.children = [None] * 128 self.is_end = False def insert(self, word): node = self for c in word: idx = ord(c) if node.children[idx] is None: node.children[idx] = Trie() node = node.children[idx] node.is_end = True class Solution: def boldWords(self, words: List[str], s: str) -> str: trie = Trie() for w in words: trie.insert(w) n = len(s) pairs = [] for i in range(n): node = trie for j in range(i, n): idx = ord(s[j]) if node.children[idx] is None: break node = node.children[idx] if node.is_end: pairs.append([i, j]) if not pairs: return s st, ed = pairs[0] t = [] for a, b in pairs[1:]: if ed + 1 < a: t.append([st, ed]) st, ed = a, b else: ed = max(ed, b) t.append([st, ed]) ans = [] i = j = 0 while i < n: if j == len(t): ans.append(s[i:]) break st, ed = t[j] if i < st: ans.append(s[i:st]) ans.append('<b>') ans.append(s[st : ed + 1]) ans.append('</b>') j += 1 i = ed + 1 return ''.join(ans)