###### tags: `Leetcode` `easy` `string` `python` `c++`

# 14. Longest Common Prefix

## [題目來源:] https://leetcode.com/problems/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 "".

## 解題想法:
找前綴字串
* 初始先找最短的字串長度作為比較長度
* n個string 比較 n-1次即可

## Python:

class Solution:
    def longestCommonPrefix(self, strs):
        ans = ""
        min_len = 200
        # Preventation
        if not strs: 
            return ans
        if len(strs) == 1: 
            return strs[0]
        # Init
        for i in strs:
            print(i)
            if len(i) < min_len:
                min_len = len(i)
                print('(最短的str)min_len:',min_len)
        # Comparison
        for i in range(min_len):
            #ex: 原本len(strs)=4 有4個str j=0,1,2,3
            #but 要倆倆依序比較: 所以讓j=0,1,2即可 才不會超出範圍
            for j in range(len(strs)-1): 
                if (strs[j][i] != strs[j+1][i]):
                    return ans
            ans = ans + strs[j][i]
        return ans
if __name__ == '__main__':
    result = Solution()
    strs = ["flower","flow","flight","flo"]
    print(result.longestCommonPrefix(strs))

## C++:

#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    string longestCommonPrefix(vector<string> &strs)
    {
        if (strs.empty())
            return "";
        if (strs.size() == 1)
            return strs[0];
        // init
        string ans = "";
        int min_len = 200;

        for (string item : strs)
        {
            if (item.size() < min_len)
                min_len = item.size();
        }
        // compare
        for (int i = 0; i < min_len; i++)
        {
            for (int j = 0; j < strs.size() - 1; j++)
            {
                if (strs[j][i] != strs[j + 1][i])
                    return ans;
            }
            ans += strs[0][i];
        }
        return ans;
    }
};
int main()
{
    Solution res;
    vector<string> strs;
    strs = {"flower", "flow", "flight"};
    cout << res.longestCommonPrefix(strs) << endl;
    return 0;
}