Problem difficulty: Easy
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 "".
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.
Solution approach
For this problem we need to compare all strings from left to right until we encounter a mismatch. Then we find the common prefix, if it’s just return “”
O(N * M) Solution (N is a length of string array. M is a length of shortest string)
For this approach we need a nested loop, the first loop we gonna loop though length of first string, the second loop will start from second element of string array. We will break this loop if we find the miss match or out of length of shortest string
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
result = ''
for i in range(len(strs[0])):
for j in range(1, len(strs)):
if i >= len(strs[j]) or strs[0][i] != strs[j][i]:
return result
result += strs[0][i]
return result
O(N) Solution N is length of the min length of word
This is a smarter approach for this solution. First, we need to find the word with the maximum length and the word with the minimum length. Then, we can find the common prefix between these two words. The idea behind this solution is that the maximum word and minimum word will have the greatest difference in length. Therefore, the common prefix between these two words is likely to be the common prefix of all the words in the string list.
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
result = ''
minWord, maxWord = max(strs), min(strs)
for i in range(len(minWord)):
if minWord[i] == maxWord[i]:
result += minWord[i]
return result
Source code: https://github.com/hongquan080799/leetcode/tree/master/longest_common_prefix
