String longest common prefix

Write a function to find the longest common prefix in the string array .

If no common prefix exists , Returns an empty string  "".

Example  1:

Input : ["flower","flow","flight"]
Output : "fl"
Example  2:

Input : ["dog","racecar","car"]
Output : ""
explain : Input does not have a common prefix .
explain :

All inputs contain only lowercase letters  a-z .

link ：https://leetcode-cn.com/problems/longest-common-prefix

 

analysis

Method 1

It's also my stupid way , Is to select a benchmark string , Then match one by one according to the prefix order , This time complexity has reached O(m*n*N) So it's bad

Method 2

utilize Python The character of string , such as aba,abb,abac Three strings ,ascall The largest size is abb, So this feature shows that there is a loop string from scratch in the comparison process , So we can ：

    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        min_str=min(strs)
        max_str=max(strs)
        for i,m in enumerate(min_str):
            if m!=max_str[i]:
                return min_str[:i]
        return min_str

Method 3

It's also the use of python Medium zip Method , use zip The built-in method aligns the left side of the string , Then compress longitudinally , And then use set Method to check the string length after de duplication ：

 def longestCommonPrefix(self, strs):
        if not strs: return ""
        ss = list(map(set, zip(*strs))) # because zip Method will finally return the Yuanzu set , So we need to use list()
        res = ""
        for i, x in enumerate(ss):
            x = list(x)
            if len(x) > 1:
                break
            res = res + x[0]
        return res

Take our input example
["flower","flow","flight"] This set uses zip After method , Namely ：

["fff","lll","ooi","wwg"]

So after the weight is removed :

["f","l","oi","wg"]

Therefore, the judgment length is greater than 1 It means that there are different letters .