Longest Common Prefix - Leetcode Solution

Problem Description: Write a function to find the longest common prefix string amongst an array of strings.

Example 1: Input: ["flower","flow","flight"] Output: "fl"

Example 2: Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

Solution: We can solve this problem by comparing the first character of each string and then moving on to the next character until we reach a character that is not common in all the strings or the end of any string is reached.

First, we check if the length of the input string array is 0 or not. If it is 0, then we return an empty string as there is no common prefix. If the input array has only one string, then we return that string as the common prefix.

We start with the first string in the input array and loop through its characters. For each character, we compare it with the first character of all other strings in the array. If we find a mismatch, then we return the substring of the first string till the position of the mismatch character as the common prefix. If we reach the end of the first string without finding any mismatches, then we add the character to the common prefix and move on to the next character of the first string.

Here is the Python code implementing the above algorithm:

def longestCommonPrefix(strs: List[str]) -> str: if len(strs) == 0: return "" if len(strs) == 1: return strs[0] prefix = "" for i in range(len(strs[0])): char = strs[0][i] for j in range(1, len(strs)): if i >= len(strs[j]) or char != strs[j][i]: return prefix prefix += char return prefix

Complexity Analysis: Time complexity: O(NM), where N is the length of the input string array and M is the length of the longest string in the array. In the worst case, we have to compare all the characters of all the strings, hence NM.

Space complexity: O(1), we are not using any extra space for the algorithm.

1