Compare characters column by column across all strings. Use the first string as a reference and check each character position against all other strings. Stop as soon as a mismatch is found or a string ends.
Sort the array of strings lexicographically. After sorting, the most different strings will be the first and last. Only compare these two to find the common prefix, since all strings in between will share at least that prefix.
""" 0014.1 - Longest Common Prefix - Solution 1 - Vertical Scanning """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def longestCommonPrefix(self, strs: List[str]) -> str:
"""Longest Common Prefix Function"""
if not strs:
return ""
for i in range(len(strs[0])):
for j in range(1, len(strs)):
if i == len(strs[j]) or strs[j][i] != strs[0][i]:
return strs[0][:i]
return strs[0]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().longestCommonPrefix(["flower", "flow", "flight"]))
print(Solution().longestCommonPrefix(["dog", "racecar", "car"]))
print(Solution().longestCommonPrefix(["interspecies", "interstellar", "interstate"]))
print(Solution().longestCommonPrefix([""]))
print(Solution().longestCommonPrefix(["a"]))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0014.2 - Longest Common Prefix - Solution 2 - Sorting Approach """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def longestCommonPrefix(self, strs: List[str]) -> str:
"""Longest Common Prefix Function"""
if not strs:
return ""
strs.sort()
first = strs[0]
last = strs[-1]
prefix = []
for i in range(len(first)):
if i < len(last) and first[i] == last[i]:
prefix.append(first[i])
else:
break
return "".join(prefix)
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().longestCommonPrefix(["flower", "flow", "flight"]))
print(Solution().longestCommonPrefix(["dog", "racecar", "car"]))
print(Solution().longestCommonPrefix(["interspecies", "interstellar", "interstate"]))
print(Solution().longestCommonPrefix([""]))
print(Solution().longestCommonPrefix(["a"]))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()