As part of the programming series, we will review the longest common prefix question which is categorized as an easy problem in Leetcode. In this exercise, we will use Python 3 to write the code.
Problem
Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “”.
- Example 1:
- Input: strs = [“flower”,”flow”,”flight”]
- Output: “fl”
- Example 2:
- Input: strs = [“dog”,”racecar”,”car”]
- Output: “”
- Explanation: There is no common prefix among the input strings.
- Constraints:
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] consists of only lowercase English letters.
Algorithm
The algorithm works by initializing the prefix as the first string in the input list. Then, it iterates through the remaining strings in the list and compares the prefix with each string. If the prefix is not a prefix of the current string, it removes the last character from the prefix and continues the comparison. This process continues until the prefix is a prefix of all the strings or until the prefix becomes an empty string.
Time complexity
- Let n be the length of the longest string in the input list and m be the number of strings in the list.
- The algorithm iterates through the list of strings once, comparing the prefix with each string.
- In the worst case, the algorithm needs to compare the prefix with all the characters in each string.
- Therefore, the time complexity is O(n * m), where n is the length of the longest string and m is the number of strings.
Space complexity
- The algorithm uses a variable to store the prefix.
- The space complexity is O(n), where n is the length of the longest string in the input list.
Code
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
# Edge case: if the list is empty, return an empty string
if not strs:
return ""
# Constraint: If the list has more than 200 strings, then return nothing
if len(strs) > 200:
return ""
# Initialize the prefix
prefix = strs[0]
# Constraint: If string length is greater than 200 chars, then return nothing
if len(strs[0]) > 200:
return ""
# Iterate through the list of strings
for i in range(1, len(strs)):
# Each string length cannot exceed 200 chars
if len(strs[i]) > 200:
return ""
# Compare the prefix with the current string
while strs[i].find(prefix) != 0:
# We remove one character at the end until we find good match
prefix = prefix[:-1]
# If we didn't find any match, return empty
if not prefix:
return ""
return prefix
if __name__ == "__main__":
strs = ["flower","flow","flight"]
solution = Solution()
print(solution.longestCommonPrefix(strs))
strs = ["dog","racecar","car"]
print(solution.longestCommonPrefix(strs))
Output
![](https://www.unbreakablecloud.com/wp-content/uploads/2024/05/image.png)
![](https://www.unbreakablecloud.com/wp-content/uploads/2024/05/image-1.png)
Happy coding! Please add your comments.