I thought I'd post my extension method in case anyone else finds it useful.

public static IHtmlString AddCssClass(this IHtmlString htmlString,
                                        IEnumerable<KeyValuePair<string, string>> tagsAndClasses)
{
    if (htmlString == null)
        return null;

    if (tagsAndClasses == null) throw new ArgumentNullException("tagsAndClasses");

    try
    {
        using (UmbracoContext.Current.Application.ProfilingLogger.DebugDuration<HtmlString>("AddCssClass"))
        {
            var tagsAndClassesArr = tagsAndClasses.AsArray();

            var str = htmlString.ToHtmlString();

             //Check if we can get away with any of the tags have a class attribute 
            //if not then otherwise a simple regex replace should work
            var simpleReplaceOkay = str.IndexOf(" class=", StringComparison.InvariantCultureIgnoreCase) < 0 ||
                                        tagsAndClassesArr
                                            .Select(pair => pair.Key)
                                            .All(tagName => !Regex.IsMatch(str, "<" + Regex.Escape(tagName) + @"\s[^>]*class.*>", 
                                                    RegexOptions.IgnoreCase | RegexOptions.Multiline));
            if (simpleReplaceOkay)
            {
                foreach (var pair in tagsAndClassesArr)
                {
                    var tagName = Regex.Escape(pair.Key);
                    var cssClass = pair.Value;
                    str = Regex.Replace(str,
                                    string.Format(@"<{0}(?=[\s>])", tagName),
                                    string.Format(@"<{0} class='{1}' ", tagName, cssClass),
                                    RegexOptions.IgnoreCase | RegexOptions.Multiline);
                }

                return new HtmlString(str);
            }

            //Full expensive HTML parse using HtmlAgilityPack
            var doc = new HtmlDocument();
            doc.LoadHtml(str);
            foreach (var pair in tagsAndClassesArr)
            {
                var tagName = pair.Key;
                var cssClass = pair.Value;

                foreach (var tag in doc.DocumentNode.SelectNodes("//" + tagName))
                {
                    var att = tag.Attributes["class"];
                    if (att == null)
                        tag.Attributes.Add("class", cssClass);
                    else
                        att.Value += " " + cssClass;
                }
            }

            var textReader = new StringWriter();
            doc.Save(textReader);

            return new HtmlString(textReader.ToString());
        }
    }
    catch (Exception exception)
    {
        LogHelper.Warn<HtmlString>("Unable to add css class to html: " + exception.Message);
    }
    return htmlString;
}

I wouldn't even worry about the regex approach you are doing. I would stick with just the "expensive HTML parse" approach instead. The performance shouldn't be that bad.

If you are really worried about performance, you could cache the conversion in a dictionary for fast lookup on subsequent conversion attempts. They key would be the original text, and the value would be the modified text.

If you went with the dictionary approach, you might be worried about memory building up. However, if this is rich text entered by users of the CMS, the variety of text that gets cached should be relatively minimal (i.e., perhaps a few thousand strings). If you really wanted to optimize for memory, you could also implement an expiring/max memory cache (i.e., entries would be removed after a certain duration, or the oldest entries would be removed after the dictionary reached a certain size).

is working on a reply...