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是數組長度。