Replacing banned words from a given text

Question

The following algorithm is used to find a word from Blacklisted words in a string (called text) and replace these words with censored text, as shown in the example.
Example:

Blacklist ["bomb"]
text: "bomb bombs"
Output: "b*** bombs"

Code

public List<string> Blacklist { get; set; } = new List<string>();

public string CensorWord(string word)
{
    if (Blacklist.Contains(word.ToLower()))
    {
        return String.Concat(word[0], new string('*', word.Length > 1 ? word.Length - 1 : 1));
    }
    else
    {
        return word;
    }
}

public string CensorText(string text)
{
    string result = text;
    foreach(string bannedWord in Blacklist) //Can I get rid of this foreach?
    {
        string pattern = String.Format(@"\b{0}\b", bannedWord);
        result = Regex.Replace(result, pattern, CensorWord(bannedWord));
    } 
    return result;
}

How can I optimize my code? I don't care about edge cases.

Answer 1

Avoid repeated calls to Contains() on a list. Each individual call has linear time complexity in size of the collection. This is usually a red flag that a set (HashSet) should be used instead.

This alone will reduce the time complexity of CensorWord from O(b) to O(1). And thus reducing time complexity of CensorText from O(b×(b+n)) to O(b×n). Where b is size of blacklist and n is size of input.

But in fact we could have done the same using a list like you do. Just don't call CensorWord from CensorText. You already know the word is coming from blacklist and so there is no need to check if blacklist indeed contains a word coming from blacklist. Just censor the word and trust that it is coming from blacklist.

Using a regex for a simple replace is probably overkill.

I can imagine that you might have a very long list of banned words while the input text may contain only few words. Using an algorithm with complexity that depends on size of blacklist may not be the best option. Instead, you can read the input text word by word, checking if each of them is on blacklist and censor them in place if they are. In this case, you will need the set for blacklist because you cannot avoid calling Contains() on the blacklist. Such implementation would be O(n) where n is size of input text.

Additionally, using a set gives us the benefit that blacklist automatically cannot contain duplicates. When using list you risk duplicates being present in blacklist or you would check it explicitly again with O(b) complexity for each individual word added to the blacklist.

Answer 2

To add to @slepic's answer regarding a set aka HashSet, you would probably want the HashSet to be case insensitive. This can simplify your code as you no longer need make calls to ToLower.

HashSet<string> Blacklist = new HashSet<string>(StringComparer.OrdinalIgnoreCase);

I am not a fan of the name CensorWord because the method may not actually censor the word but rather returns the original word uncensored.

I am hoping this is really a homework assignment and not something work related. There is a greater chance of utter futility and frustration if this was to be something practical for work. Chalk this up to the ingenuity of creative people who can deviously design workarounds to your censorship. If you censor "bomb", I could come up with dozens of ways to convey the same thing: "b-o-m-b", "b-omb", "b o m b", and that's just using blanks and dashes. I could use dozens of other special characters. Sure you can add them to your blacklist, but (1) you would always be reactive-after-the-fact to new spellings, and (2) you are now faced with task of how to update the blacklist.