Find and replace String with a substring result

Question

I was asked this recently, and I couldn't figure out the best way. We are trying to replicate Google's search results where the search terms are bolded (using a b tag) in the results.

Input                       Terms               Output
The search is cool          {sea}               The <b>sea</b>rch is cool

Originally, I thought this was pretty easy:

String results(String input, String[] terms)
{
   for(String term : terms)
   {
      input = input.replace(term, "<b>" + term + "</b>");
   }

   return input;
}

However, this isn't correct. For example:

Input                       Terms               Output
The search is cool          {sea, search}       The <b>search</b> is cool

I struggled to figure out the best way to approach this. Obviously we can no longer find and replace immediately. I played around with using a Map<Integer,String> where the key is the index returned by input.indexOf(term) and the value is the term, but this seemed potentially unnecessary. Any improvements?

public String results(String input, String[] terms)
{
   Map<Integer, String> map = new HashMap<Integer,String>();
   for(String term : terms)
   {
      int index = input.indexOf(term);
      if(index >= 0)//if found
      {
          String value = map.get(index);
          if(value == null || value.length() < term.length())//use the longer term
              map.put(index, term);
      }


   }

   for(String term: map.values())
   {
       input = input.replace(term, "<b>" + term + "</b>");
   }

   return input;
}

Answer 1

I would go with Regex for this, with greedy matches so that nested results like your example above would only match the outer string.

So with your example here:

Input                       Terms               Output
The search is cool          {sea, search}       The <b>search</b> is cool

A Regex pattern of search|sea could be derived from the search terms, and only 'search' would be matched. Note that the longest term will need to first for this to work as desired.

String results(String input)
{
 String retVal = input.replaceAll("search|sea", "<b>$1</b>")

 return input;
}

I think this should be close to what you need, but I havn't had time to test and check. Hope it helps.

Answer 2

The second version looks fine. Anyway, two other quick ideas:

1. Consider replacing only complete words (substrings which has whitespace before and after).

2. Sort the term list by length (descending) and ABC then replace every occurrence only once. StringUtils.replaceEach from Apache Commons Lang supports that.

   String input = "The sea search is cool";
   String[] terms = new String[] { "search", "sea" };
   String[] replacementList = new String[] { "<b>search</b>", "<b>sea</b>" };
   String output = StringUtils.replaceEach(input, terms, replacementList);
   System.out.println(output);
   

   The output is the following:

   String input = "The sea search is cool";
   String[] terms = new String[] { "search", "sea" };