---
# System prepended metadata

title: 14. Longest Common Prefix
tags: [LeetCode]

---

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


輸入範本如下
```C#
public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        
    }
}
```


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

```C#
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        |

```C#
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
    - 將字串組不斷分成兩半去比較.

```C#
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: 
