题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:
所有输入只包含小写字母 a-z 。

题解

纵向扫描

纵向扫码的优势在于当存在不同字符时，能最快的结束扫描。
下面的代码通过将同一位置的字符 Select 出来，再 Count 不同的字符数，仅在字符全相同时 Count 结果才为 1。

public string LongestCommonPrefix(string[] strs)
{
    if (strs == null || strs.Length == 0) return "";
    if (strs.Length == 1) return strs[0];
    var minLength = strs.Min(s => s.Length);
    var commonPrefix = "";
    for (var i = 0; i < minLength; i++)
    {
        var count = strs.Select(s => s[i]).Distinct().Count();
        if (count > 1) break;
        commonPrefix += strs[0][i];
    }
    return commonPrefix;
}

Binary Search

参考官方，方法如图：
二分搜索，搜索到第一个不相等的部分暂停。

public static string LongestCommonPrefix(string[] strs)
{
    if (strs == null || strs.Length == 0) return "";
    if (strs.Length == 1) return strs[0];
    var minLength = strs.Min(s => s.Length);
    var low = 1;
    var high = minLength;
    while (low <= high)
    {
        var middle = (low + high) / 2;
        if (IsCommonPrefix(strs, middle))
        {
            low = middle + 1;
        }
        else
        {
            high = middle - 1;
        }
    }
    return strs[0].Substring(0, (low + high) / 2);
}
private static bool IsCommonPrefix(IReadOnlyList<string> strs, int len)
{
    var str1Prefix = strs[0].Substring(0, len);
    for (var i = 1; i < strs.Count; i++)
    {
        if (!strs[i].StartsWith(str1Prefix)) return false;
    }
    return true;
}