---
tags: LeetCode
---

# 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.

輸入範本如下

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        
    }
}

### 直覺想法
1. 使用第一個字串做為基準 , 然後去比第二個字串 , 找出兩者的 LongestCommonPrefix , 在拿這個 LongestCommonPrefix 繼續比第三個字

204 ms	24.6 MB
faster than 5.13% of C# online submissions for Longest Common Prefix.
public string LongestCommonPrefix(string[] strs)
{
    if (strs.Length == 0) return string.Empty;

    string commonPrefix = strs.First();
    for (int i = 1; i < strs.Length; i++)
    {
        int index;
        for (index = 0; index < commonPrefix.Length && index < strs[i].Length && commonPrefix[index] == strs[i][index]; index++) ;
        commonPrefix = commonPrefix.Substring(0, index);
    }
    return commonPrefix;
}

2. 把每一個字串排在一起比較
- 先對第一個字 f 是否都有 , 在繼續往下對第二個字 l 是否都有 , 在第三個字 o 發現沒有都有 , 則回傳答案 fl

| string[] strs |
| ------------- |
| flower |
| flow |
| flight |

88 ms	24.7 MB
You are here!
Your runtime beats 99.50 % of csharp submissions.
public string LongestCommonPrefix(string[] strs)
{
    if(strs.Length==0) return String.Empty;
    StringBuilder commonPrefix = new StringBuilder();
    for (int i = 0; i < strs[0].Length; i++)
    {
        foreach (string str in strs)
        {
            if (str.Length <= i || str[i] != strs[0][i])
            {
                return commonPrefix.ToString();
            }
        }
        commonPrefix.Append(strs[0][i]);
    }
    return commonPrefix.ToString();
}

3. 使用策略 Divide and conquer
- 將字串組不斷分成兩半去比較.

120 ms	24.1 MB
You are here!
Your runtime beats 17.14 % of csharp submissions.
public string LongestCommonPrefix(string[] strs)
{
     if (strs == null || strs.Length == 0) return string.Empty;
         return longestCommonPrefix(strs, 0, strs.Length - 1);

     string longestCommonPrefix(string[] strArr, int l, int r)
     {
          if (l == r)
          {
               return strArr[l];
          }
          int mid = l + (r - l) / 2;
          string lcpLeft = longestCommonPrefix(strArr, l, mid);
          string lcpRight = longestCommonPrefix(strArr, mid + 1, r);
          return commonPrefix(lcpLeft, lcpRight);
     }

     string commonPrefix(string left, string right)
     {
          int min = Math.Min(left.Length, right.Length);
          for (int i = 0; i < min; i++)
          {
               if (left[i]!= right[i])
                    return left.Substring(0, i);
          }
          return left.Substring(0, min);
     }
}

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: