Find first difference in strings case insensitive given culture

Question

There are many ways to compare two strings to find the first index where they differ, but if I require case-insensitivity in any given culture, then the options go away.

This is the only way I can think to do such a comparison:

static int FirstDiff(string str1, string str2)
{
    for (int i = 1; i <= str1.Length && i <= str2.Length; i++)
        if (!string.Equals(str1.Substring(0, i), str2.Substring(0, i), StringComparison.CurrentCultureIgnoreCase))
            return i - 1;
    return -1; // strings are identical
}

Can anyone think of a better way that doesn't involve so much string allocation?

For testing purposes:

// Turkish word 'open' contains the letter 'ı' which is the lowercase of 'I' in Turkish, but not English
string lowerCase = "açık";
string upperCase = "AÇIK";

Thread.CurrentThread.CurrentCulture = new CultureInfo("en-US");
FirstDiff(lowerCase, upperCase); // Should return 2

Thread.CurrentThread.CurrentCulture = new CultureInfo("tr-TR");
FirstDiff(lowerCase, upperCase); // Should return -1

Edit: Checking both ToUpper and ToLower for each character appears to work for any example that I can come up with. But will it work for all cultures? Perhaps this is a question better directed at linguists.

Answer 1

One way to reduce the number of string allocations is to reduce the number of times you do a comparison. We can borrow from the binary search algorithm for searching arrays in this case, and start out by comparing a substring that is half the length of the string. Then we continue to add or remove half of the remaining indexes (depending on whether or not the strings were equal), until we get to the first instance of inequality.

In general this should speed up the search time:

public static int FirstDiffBinarySearch(string str1, string str2)
{
    // "Fail fast" checks
    if (string.Equals(str1, str2, StringComparison.CurrentCultureIgnoreCase))
        return -1;
    if (str1 == null || str2 == null) return 0;

    int min = 0;
    int max = Math.Min(str1.Length, str2.Length);
    int mid = (min + max) / 2;

    while (min <= max)
    {               
        if (string.Equals(str1.Substring(0, mid), str2.Substring(0, mid), 
            StringComparison.CurrentCultureIgnoreCase))
        {
            min = mid + 1;                    
        }
        else
        {
            max = mid - 1;
        }

        mid = (min + max) / 2;
    }

    return mid;
}

Answer 2

You need to check both ToLower and ToUpper.

private static int FirstDiff(string str1, string str2)
{
    int length = Math.Min(str1.Length, str2.Length);
    TextInfo textInfo = CultureInfo.CurrentCulture.TextInfo;
    for (int i = 0; i < length; ++i)
    {
        if (textInfo.ToUpper(str1[i]) != textInfo.ToUpper(str2[i]) ||
            textInfo.ToLower(str1[i]) != textInfo.ToLower(str2[i]))
        {
            return i;
        }
    }
    return str1.Length == str2.Length ? -1 : length;
}

Answer 3

You could compare characters instead of strings. This is far from optimized, and rather quick and dirty, but something like this appears to work

for (int i = 0; i < str1.Length && i < str2.Length; i++)
   if (char.ToLower(str1[i]) != char.ToLower(str2[i]))
       return i;

This should work with culture as well, according to the docs: https://learn.microsoft.com/en-us/dotnet/api/system.char.tolower?view=netframework-4.8

Casing rules are obtained from the current culture.

To convert a character to lowercase by using the casing conventions of the current culture, call the ToLower(Char, CultureInfo) method overload with a value of CurrentCulture for its culture parameter.

Answer 4

I am reminded of one additional oddity of characters (or rather unicode code points): there are some that act as surrogate pairs and they have no relevance to any culture unless the pair appears next to one another. For more information about Unicode interpretation standards see the document that @orhtej2 linked in his comment.

While trying out different solutions I stumbled upon this particular class, and I think it will best suit my needs: System.Globalization.StringInfo (The MS Doc Example shows it in action with surrogate pairs)

The class breaks the string down into sections by pieces that need each other to make sense (rather than by strictly character). I can then compare each piece by culture using string.Equals and return the index of the first piece that differs:

static int FirstDiff(string str1, string str2)
{
    var si1 = StringInfo.GetTextElementEnumerator(str1);
    var si2 = StringInfo.GetTextElementEnumerator(str2);

    bool more1, more2;
    while ((more1 = si1.MoveNext()) & (more2 = si2.MoveNext())) // single & to avoid short circuiting the right counterpart
        if (!string.Equals(si1.Current as string, si2.Current as string, StringComparison.CurrentCultureIgnoreCase))
            return si1.ElementIndex;

    if (more1 || more2)
        return si1.ElementIndex;
    else
        return -1; // strings are equivalent
}

Answer 5

Here's a little different approach. Strings are technically arrays of char, so I'm using that along with LINQ.

var list1 = "Hellow".ToLower().ToList();
var list2 = "HeLio".ToLower().ToList();

var diffIndex = list1.Zip(list2, (item1, item2) => item1 == item2)
                .Select((match, index) => new { Match = match, Index = index })
                .Where(a => !a.Match)
                .Select(a => a.Index).FirstOrDefault();

If they match, diffIndex will be zero. Otherwise it will be the index of the first mismatching character.

Edit:

A little improved version with casting to lower case on the go. And initial ToList() was really redundant.

var diffIndex = list1.Zip(list2, (item1, item2) => char.ToLower(item1) == char.ToLower(item2))
                .Select((match, index) => new { Match = match, Index = index })
                .Where(a => !a.Match)
                .Select(a => a.Index).FirstOrDefault();

Edit2:

Here's a working version where it can be further shortened. This is the best answer since in the previous two you'll get 0 if strings match. Here' if strings match you get null and the index otherwise.

var list1 = "Hellow";
var list2 = "HeLio";

var diffIndex = list1.Zip(list2, (item1, item2) => char.ToLower(item1) == char.ToLower(item2))
                .Select((match, index) => new { Match = match, Index = index })
                .FirstOrDefault(x => !x.Match)?.Index;