14. Longest Common Prefix

• python3

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.

Pseudocode

First Soluton

1. Initialize the prefix with the value of the first string.
2. Compare the strings by iterating through each character up to the length of the shorter string. 3. If the characters match, add the character to a temporary variable (temp). If they differ, break the loop, update the prefix with the value of temp, and proceed to compare the next string.
3. Return the prefix.

Second Soluton

1. Sort the array.
2. Compare the first and last strings.
3. Return the prefix.

Code

First Soluton

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:

        prefix = strs[0]

        for i in range(1, len(strs)):
            minLen = min(len(prefix),len(strs[i]))
            temp = ""
            for j in range(minLen):
                if prefix[j] == strs[i][j]:
                    temp += prefix[j]
                else:
                    break 
            prefix = temp

        return prefix

Second Soluton

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:

        ans=""
        strs=sorted(strs)
        first=strs[0]
        last=strs[-1]
        for i in range(min(len(first),len(last))):
            if(first[i]!=last[i]):
                return ans
            ans+=first[i]
        return ans 

Result

first solution

• Time Complexity: O(n^2)
• Space Complexity: O(1)

second Solution

• Time Complexity:O(n log n) as sorted methods
• Space Complexity: Technically, O(n). But it seems to O(1)