Leetcode 14: Longest Common Prefix

Problem Description

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 “”.

Thought Process

First I thought about sorting the strs array based on string length so I would not have to worry about indexing out of bounds. However I quickly realised that I could just use the first string in the array as a reference and check each character of the other strings against it. If they are not equal, I can break out of the loop and return the prefix up to that point. Also good thing to notice is that we do not need to explicitly check for strs array being empty since the problem statement guarantees that the input will be a non-empty array of strings.

Code

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for i,c in enumerate(strs[0]):
            for string in strs:
                if i>=len(string) or c!=string[i]:
                    return strs[0][:i]
        return strs[0]

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n*m) where n is the number of strings in the array and m is the length of the longest common prefix shared with the strings. This is because we are iterating through each character of the first string and checking it against each string in the array.

Space Complexity

The space complexity is O(1) since we are not using any additional data structures to store intermediate results.

Difficulty

This problem is considered easy on Leetcode. The problem really was easy, probably easiest I have seen on leetcode so far.