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: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

My first try

The simplest way to loop through each character and each word to compare the difference. It can early stop if there is a difference occur.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        max_prefix = 0
        for index, character in enumerate(strs[0]):
            for string in strs:
                if len(string) < (index + 1):
                    return strs[0][:max_prefix]
                if string[index] != character:
                    return strs[0][:max_prefix]
            max_prefix += 1
        
        return strs[0][:max_prefix]

The worst case can be O(strs.length * strs[i].length).

My second try

After looking into some solutions, it can improve by sorting the words first and compare the first and the last word. Sorting strs, it’s sorted word by word and character by character.

For example,

a = ["fly", "flight", "flower"]

print(sorted(a)) # you will get ["flight", "flower", "fly"]

Therefore, it only needs to compare the first and the last word.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans = ""
        strs=sorted(strs)
        first=strs[0]
        last=strs[-1]
        for i in range(min(len(first),len(last))):
            if(first[i]!=last[i]):
                return ans
            ans+=first[i]
        return ans