BFE.dev is like a LeetCode for Front End developers. I’m using it to practice my skills.
This article is about the coding problem BFE.dev#55. highlight keywords in HTML string
Analysis
The goal is to wrap keywords with <em>.
highlightKeywords(
'Hello FrontEnd Lovers',
['Hello', 'Front', 'JavaScript']
)
// '<em>Hello</em> <em>Front</em>End Lovers'
Looks easy, just search for the keywords and replace them. But it is trickier when there are overlapping keywords
highlightKeywords(
'Hello FrontEnd Lovers',
['Front', 'FrontEnd', 'JavaScript']
)
// 'Hello <em>FrontEnd</em> Lovers'
The idea I came up is like this.
- when we find a keyword, say
'Front'in above example, we keep track of thestartandend. - we loop through the letters between them, and check if there is new word matched. If matched we extend the
endif needed, this is in case there are some keywords likeontE. - stop when
endis met. The substring betweenstartandendshould be highlighted.
Above logic handles overlapping, what about adjacent case ?
highlightKeywords(
'Hello FrontEnd Lovers',
['Front', 'End', 'JavaScript']
)
// 'Hello <em>FrontEnd</em> Lovers'
For this case, we could actually repeatedly search for the intervals from above logic, and group them up.
Show me the code
First we solve a sub problem:
Given a start index, return the end index of highlighting substring.
If not found, return -1.
We could follow the steps explained above to get the following code.
const keywordSet = new Set(keywords)
// return -1 if non-existing
const getEndForEm = (start) => {
let isEmFound = false
let end = start
// extend end if new keywords are matched.
while (start <= end) {
for (let word of keywordSet) {
const length = word.length
if (html.slice(start, start + length) === word) {
isEmFound = true
end = Math.max(end, start + length - 1)
}
}
start += 1
}
return isEmFound ? end : -1
}
Now things become easier, we could just loop through all the indexes, and repeatedly call above function to get the real end index to highlight.
let result = ''
for (let i = 0; i < html.length;) {
let endForEm = getEndForEm(i)
// check if there is adjacent keyword
while (endForEm > -1) {
const nextEndForEm = getEndForEm(endForEm + 1)
if (nextEndForEm === -1) {
break
}
endForEm = nextEndForEm
}
if (endForEm > -1) {
result += '<em>' + html.slice(i, endForEm + 1) + '</em>'
i = endForEm + 1
} else {
result += html[i]
i += 1
}
}
return result
Passed
This is an interesting problem.
Hope it helps, you can have a try at here
Top comments (0)