# 14-Longest Common Prefix
###### tags: `Easy`

## Question
https://leetcode.com/problems/longest-common-prefix/

## Solution
### C++ space 92% time 34%

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ans;
        for(int i = 0; i < strs[0].size();i++)
        {
            char tmp = strs[0][i];
            for(int j = 1; j < strs.size();j++)
            {
                if(tmp != strs[j][i])
                {
                   return ans;
                }
            } 
            ans += tmp;
        }
        return ans;
        
    }
};

### space 78% time 100%
直接假設第一個是prefix，所以只要比較size-1個單字，但要不停調整單字長度

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // assume the first string is the longest prefix
        int maxlen = strs[0].size();
        for(int i = 1; i < strs.size(); i++) 
        {
            // prefix can only be minimum of two strs we compare 
            maxlen = min(maxlen, (int)strs[i].size());
            int currlen = 0;
            for(int j = 0; j < maxlen; j++) 
            {
                if(strs[i][j] != strs[i-1][j])
                    break;
                ++currlen;
            }
            // if curr prefix len is less than curr maxlen then the
            // prefix cannot be more than current length
            maxlen = currlen;
        }
        return strs[0].substr(0, maxlen);
    }
};

### Python
- 想法:每個字串都要有相同的prefix，而不是找出現最多的prefix，否則都為""，因此字母循序往後找即可

class Solution(object):
    def longestCommonPrefix(self, strs):
        common_prefix = strs[0]

        for i, curr_str in enumerate(strs):
            if len(curr_str)<len(common_prefix):
                common_prefix = curr_str 

        if common_prefix == "":
            return ""

        for i in range(len(common_prefix)):
            match = True 
            for string in strs:
                if string[i]!=common_prefix[i]:
                    match=False 
            if not match:
                return common_prefix[:i] 

        return common_prefix