14_Longest Common Prefix

[easy] [string]

Write a function to find the longest common prefix string amongst an array of strings. All given inputs are in lowercase lettersa-z. If there is no common prefix, return an empty string"".

Example 1:

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

Example 2:

Input: ["dog","racecar","car"]
Output: ""

Solution: vertical scanning

Idea:

• scan over each column, check if the characters are the same.

Time Complexity: $O(mn)$ m is the number of strings in the input, n is the min length of the strings.

Space Complexity: $O(1)$

def longestCommonPrefix(strs):
    """
    :type strs: List[str]
    :rtype: str
    """
    if not strs: return ''
    out = []
    i = 0
    n = min([len(word) for word in strs])
    for i in range(n):
        l = list(strs[0])[i]
        for j in range(1, len(strs)):
            if list(strs[j])[i] != l:
                return ''.join(out)
        out.append(l)
    return ''.join(out)