[LeetCode][python3]0014. Longest Common Prefix

Start the Journey
N2I -2020.03.18

1. My first try

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if strs:
            min_len=len(min(strs,key = len))
            for i in range(min_len):
                c=min(strs,key = len)[i]                
                for s in strs:
                    if s[i]!=c:
                        if i==0:
                            return ""
                        return min(strs,key = len)[0:i]
                        break
            return min(strs,key = len)
        else:
            return ""

Explanation:

A normal way to think about this problem. The solution compares chars from the smallest length string of strs to other strings in strs. The for loop will stop when someone diff from the compare.

2. A better Solution

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:return ""
        m,M,i=min(strs),max(strs),0
        for i in range (min(len(m),len(M))):
            if m[i]!=M[i]:break
        else:
            i=i+1
        return m[:i]

Explanation:

The solution takes advantage from the “Comparative of String objects”. The biggest different in sequence will appear in the comparison of min(strs) and max(strs). That is why the solution only compares those two strings in list. It is same idea when you check out the first vocabulary and the last vocabulary in your English Dictionary and you will confirm every vocabulary between them will share the same prefix if the first and the last vocabulary shares them.