LeetCode | Longest Common Prefix | Geek Hacker

Problem Statement

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 "".

Constraints

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

Examples

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.

Analysis

A prefix is a collection of characters at the beginning of a string. For instance, “mi” is a prefix of “mint” and the longest common prefix between “mint”, “mini”, and “mineral” is “min”.

In order to find the longest common prefix, we sort the array of strings alphabetically. Then, we compare the characters in the first and last strings in the array. If the character in first is in last at the corresponding index, the character must be in the remaining words at the corresponding index as well, because the array of strings have already been sorted.

Algorithm

1. Sort the array of strings in alphabetical order.
2. Compare the characters in the first and last strings in the array.
3. If they are same, then append the character to the result.
4. Else, stop the comparison — result contains the longest common prefix among the strings in the array.

Python 3 Code

def longestCommonPrefix(self, strs):
   longest_pre = []
 
   if strs and len(strs) > 0:
      strs = sorted(strs) 
      first, last = strs[0], strs[-1] 
      for i in range(len(first)):
         if len(last) > i and last[i] == first[i]:
            longest_pre.append(last[i])
         else:
            return “”.join(longest_pre)
   return “”.join(longest_pre)

For more LeetCode problems’ solutions, visit my GitHub repo.

If you enjoyed reading this article, please recommend and share it to help others find it!