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是数组长度。
内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!