algoadvance

Before we jump into the coding, it’s important to clarify what we need to do:

1. Input/Output:
   • Input: Is a list of strings. For example, ["flower","flow","flight"].
   • Output: A string that represents the longest common prefix of the input list. For example, "fl" for the input example provided.
2. Edge Cases:
   • What if the list is empty?
   • What if there is only one string in the list?
   • What if no common prefix exists?
3. Constraints:
   • Are all strings lowercase?
   • Is there a limit on the length of the strings or the number of strings?

Strategy:

1. Horizontal Scanning Approach:
   • Start by assuming the first string is the prefix.
   • Compare this prefix against each subsequent string and reduce the prefix length until it becomes the common prefix for all strings.
   • If at any point the prefix becomes an empty string, return an empty string immediately.
2. Implementation Steps:
   1. Handle edge cases (empty list, single string in list).
   2. Initialize the prefix as the first string.
   3. Iterate through the rest of the strings, adjusting the prefix as required.
   4. Return the final computed prefix.

Time Complexity:

• Time Complexity: O(S), where S is the sum of all characters in all strings. This is because at most we check each character of each string.
• Space Complexity: O(1), since we use constant extra space.

Code:

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    # Start by assuming the first string is the common prefix
    prefix = strs[0]
    
    # Loop through the rest of the strings
    for string in strs[1:]:
        # Adjust the prefix length until it matches the start of the current string
        while not string.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    
    return prefix

# Example usage
print(longestCommonPrefix(["flower", "flow", "flight"]))  # Output: "fl"
print(longestCommonPrefix(["dog", "racecar", "car"]))    # Output: ""
print(longestCommonPrefix([]))                           # Output: ""
print(longestCommonPrefix(["alone"]))                    # Output: "alone"

Explanation:

• Lines 2-3: Handle the case where the input list is empty.
• Line 6: Initialize the prefix as the first string in the list.
• Lines 9-15: Iterate over each string in the list starting from the second one. Adjust the prefix by slicing off its end until it matches the start of the current string.
• Lines 11-13: If at any point the prefix becomes an empty string, return immediately.
• Line 17: After the loop, return the remaining prefix.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?