""" 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()