# Longest Common Prefix ## # Solution

lcp means "longest common prefix".

Let S be the summed length of all strings.

### # Horizontal Scanning

Initialize lcp as strs, 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

lcp = strs
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[i]. If not, return strs[:i]. After nested for loop, return the lcp as strs.

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

Complexity:

• Time:
• best case: strs == ""
• 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

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


### # 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

strs.sort()
lcp = ""

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

Last Updated: 5/13/2020, 7:39:18 AM