Find and replace String with a substring result 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 &lt;b&gt;sea&lt;/b&gt;rch is cool


Originally, I thought this was pretty easy:

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

   return input;
}


However, this isn't correct. For example:

Input                       Terms               Output
The search is cool          {sea, search}       The &lt;b&gt;search&lt;/b&gt; 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&lt;Integer,String&gt; 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&lt;Integer, String&gt; map = new HashMap&lt;Integer,String&gt;();
   for(String term : terms)
   {
      int index = input.indexOf(term);
      if(index &gt;= 0)//if found
      {
          String value = map.get(index);
          if(value == null || value.length() &lt; term.length())//use the longer term
              map.put(index, term);
      }


   }

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

   return input;
}
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 &lt;b&gt;search&lt;/b&gt; 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", "&lt;b&gt;$1&lt;/b&gt;")

 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.