LeetCode 14 - Longest Common Prefix - Python

 

Question:

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.

Answer:

To find the longest common prefix among an array of strings, we can compare the characters of all strings from left to right until we encounter a mismatch. The common prefix will be the characters that are the same for all strings until the first mismatch.

Approach:

1. If the input array strs is empty, return an empty string because there is no common prefix.
2. Initialize a variable prefix with an initial value equal to the first string in the array strs[0].
3. Iterate through the rest of the strings in the array strs starting from the second string (index 1).
4. For each string in the array, compare its characters with the characters of the prefix string.
5. While comparing, if we find a mismatch between the characters or if the prefix becomes empty, return the current value of prefix as the longest common prefix.
6. After iterating through all strings, return the final value of prefix as the longest common prefix.

Time complexity:

O(n * m), where n is the number of strings in the array, and m is the length of the longest string.

Space complexity:

O(m), where m is the length of the longest string, as we store the prefix string.

Code:

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        prefix = strs[0]
        for string in strs[1:]:
            while string.find(prefix) != 0:
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        return prefix