BFE.dev #55. highlight keywords in HTML string

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.

1. when we find a keyword, say 'Front' in above example, we keep track of the start and end.
2. we loop through the letters between them, and check if there is new word matched. If matched we extend the end if needed, this is in case there are some keywords like ontE.
3. stop when end is met. The substring between start and end should 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