Leetcode 14. Longest Common Prefix
Explanation for Leetcode 14 - Longest Common Prefix, and its solution in Python.
Problem
Leetcode 14 - Longest Common Prefix
Example:
1
2
3
4
5
6
Input: strs = ["flower","flow","flight"]
Output: "fl"
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Approach
We can first sort the array so it returns the sorted array of strings by lexicographically. Meaning that in example of “flower, flow, flight”, the sorted result should be “flight, flow, flower”. Now from here since we’re only looking for common prefixes, we can compare just the first element and the last element as all the strings in the middle should either have common prefix, if not since last element is lexicographically last, character should be different compared to first element.
Visualization of the approach:
1
2
3
4
5
6
7
8
Input: ["flower", "flow", "flight"]
After sorting: ["flight", "flow", "flower"]
First element: flight
Last element: flower
Since "fl" is the only common prefix, result should be "fl"
Here is the Python code for the solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def longestCommonPrefix(self, strs:List[str]) -> str:
#initializing result
res = ""
#sort the array lexicographically and get first and last element of the array
strs = sorted(strs)
first = strs[0]
last = strs[-1]
# we compare each character of first and last (we only need to iterate through min of either first or last)
for i in range(min(len(first), len(last))):
# if we find a different character we return result
if (first[i] != last[i]):
return res
# else we add that character to the result
res += first[i]
return res
Time Complexity and Space Complexity
$m$ is equal to length of the array(strs)
$n$ is equal to length of the min length of either first or last element in array
Time Complexity: $O(n*m log(m))$ since we are sorting the list, and we’re iterating the min length of either first or last element in array.
Space Complexity: $O(1)$ or $O(m)$ depending on sorting algorithm that we use.