C# 写 LeetCode easy #14 Longest Common Prefix

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是数组长度。