C# 写 LeetCode easy #14 Longest Common Prefix

来源：cnblogs　　作者：皮皮丶码　　时间：2018/11/30 9:43:07　　对本文有异议

14、Longest Common Prefix

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: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

代码：

static void Main(string[] args)
{
    string[] str = new string[] { "my","myname","mys"};
    string res=GetLongestCommonPrefix(str);
    Console.WriteLine(res);
    Console.ReadKey();
}
private static string GetLongestCommonPrefix(string[] strs)
{
    if (strs.Length == 0) return "";
    if (strs.Length == 1) return strs[0];
    var min = int.MaxValue;
    foreach (var item in strs)
    {
        if (item.Length < min)
        {
            min = item.Length;
        }
    }
    var index = -1;
    for (int i=0; i < min; i++)
    {
        for (int j = 1; j < strs.Length; j++)
        {
            if (strs[j][i] != strs[0][i])
            {
                return strs[0].Substring(0, i);
            }
            else
            {
                index = i;
            }
        }
    }
    return strs[0].Substring(0,index+1);
}

解析： 
输入：字符串数组
输出：字符串
思想：
　　首先，分三部分，当数组为空时，返回空字符串；数组中只有一个元素，输出该元素；数组中有若干字符串，则进行以下操作。(注意：这里也可以判断数组中是否含有空字符串，有则返回空)
　　其次，对于一般情况，先找出数组中最小长度的字符串，根据这个长度，从第一个字符开始遍历。
　　最后，将数组中的每个字符串和第一个字符串的每个字符进行比较。相同则记录字符索引值，否则返回共同子串。
时间复杂度：O(m*n)   其中m是单词最大长度，n是数组长度。