C# LeetCode 14: Longest Common Prefix

Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Code

public string LongestCommonPrefix(string[] strs)
{
    if (strs == null || strs.Length == 0)
        return "";

    if (strs.Length == 1)
        return strs[0];

    string prefix = strs[0];

    for (int i = 1; i < strs.Length; i++)
    {
       while (!strs[i].StartsWith(prefix, StringComparison.Ordinal))
        {
            prefix = prefix[..^1]; 

            if (string.IsNullOrEmpty(prefix))
                return "";
        }
    }

    return prefix;
}

Approach

Keep it simple is the best approach, my first attempt was quite verbose, so I refactored down to this. The basic premise is:

1. Start with an optimistic prefix
   Assume the first string is the full prefix.

2. Iterative shrinking
   For each other string, check if it starts with the current prefix.
   If not, shrink the prefix from the end until it matches or becomes empty.

3. Early exit
   If the prefix ever becomes empty, return "" immediately (no common prefix exists).

And there you have it a nice, simple way to find the longest common pre-fix :)

As always if you want to learn more, or see other articles in the series drop me a follow here, or on twitter / x