Compare characters column by column across all strings. For each index, check if every string has the same character at that position. Stop as soon as a mismatch is found or a string ends.
Sort the array lexicographically. The longest common prefix of the entire array must be the common prefix of the first and last strings after sorting, since they are the most different.
""" 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])):
char = strs[0][i]
for s in strs[1:]:
if i >= len(s) or s[i] != char:
return strs[0][:i]
return strs[0]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().longestCommonPrefix(["flower", "flow", "flight"])) # "fl"
print(Solution().longestCommonPrefix(["dog", "racecar", "car"])) # ""
print(Solution().longestCommonPrefix(["interspecies", "interstellar", "interstate"])) # "inters"
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0014.2 - Longest Common Prefix - Solution 2 - Sorting and Comparing Extremes """
#####################################################################################
# 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, last = strs[0], strs[-1]
i = 0
while i < len(first) and i < len(last) and first[i] == last[i]:
i += 1
return first[:i]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().longestCommonPrefix(["flower", "flow", "flight"])) # "fl"
print(Solution().longestCommonPrefix(["dog", "racecar", "car"])) # ""
print(Solution().longestCommonPrefix(["interspecies", "interstellar", "interstate"])) # "inters"
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()