# Problem

problem at: https://leetcode.com/problems/longest-common-prefix

# Solution

lcp means "longest common prefix".

Let S be the summed length of all strings.

# Horizontal Scanning

Initialize lcp as strs[0], then iterate thru strs[1:] and truncate lcp by ending char if not found.

The commented line handles the case when only 1 string is in list. Not needed for this solution, but important for following ones.

Complexity:

  • Time:
    • best case: there are at most comparisons ( is the length of the shortest string in the array)
    • worst case: all n strings are the same
  • Space:
def longestCommonPrefix(self, strs: List[str]) -> str:
    if not strs: return ""
    # if len(strs) == 1: return strs[0]

    lcp = strs[0]
    for i in range(1,len(strs)):
        while strs[i].find(lcp)!=0:
            lcp = lcp[:-1]
    return lcp

# Vertical Scanning

Vertically scan thru strs[1:] to see if each string has the ith char is the same as strs[0][i]. If not, return strs[0][:i]. After nested for loop, return the lcp as strs[0].

Similar to horizontal scanning, vertical scanning has same time & space complexity.

Complexity:

  • Time:
    • best case: strs[0] == ""
    • worst case: all n strings are the same (same as that in Horizontal Scanning)
  • Space:
def longestCommonPrefix(self, strs: List[str]) -> str:
    if not strs: return ""
    if len(strs) == 1: return strs[0]

    for i in range(0,len(strs[0])):
        c = strs[0][i]
        for j in range(1, len(strs)):
            if i==len(strs[j]) or strs[j][i] != c:
                return strs[0][:i]
    return strs[0]

# Sort & Compare 1st and last

Sort strs s.t. elements are in alphabetical order. Then zip the 1st and last strings to extract the lcp. Very elegant solution!

Complexity:

  • Time:
  • Space:
def longestCommonPrefix(self, strs: List[str]) -> str:
    if not strs: return ""
    if len(strs) == 1: return strs[0]

    strs.sort()
    lcp = ""

    for s,t in zip(strs[0], strs[-1]):
        if s == t: lcp += s
        else: break
    return lcp