💡 Problem Formulation: Given an array of words, the task is to find the length of the longest common prefix among these words. The solution should return 0 if there is no common prefix. For instance, with the input array [“flower”,”flow”,”flight”], the desired output is 2, as the longest common prefix is “fl”.
Method 1: Horizontal Scanning
The Horizontal Scanning method iterates through the words in the array, comparing characters of the current longest common prefix with the next word character by character, to determine the longest common prefix sequence. The time complexity is O(S), where S is the sum of all characters in all words.
Here’s an example:
def longest_common_prefix(strs):
if not strs:
return ""
prefix = strs[0]
for word in strs[1:]:
while word.find(prefix) != 0: # Index of the found prefix
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
print(longest_common_prefix(["flower","flow","flight"]))
Output: “fl”
The function takes a list of words and initializes the prefix with the first word. It then goes through each word, trimming the prefix until it matches the start of the word or is empty.
Method 2: Vertical Scanning
Vertical Scanning compares characters from the top down at the same index of all words. It stops when a mismatch is found or the end of a word is reached. This can be more efficient than Horizontal Scanning if there is a very short prefix or a short word early in the list.
Here’s an example:
def longest_common_prefix(strs):
if not strs: return ""
for i in range(len(strs[0])):
for word in strs[1:]:
if i == len(word) or word[i] != strs[0][i]:
return strs[0][:i]
return strs[0]
print(longest_common_prefix(["flower","flow","flight"]))
Output: “fl”
This function iterates character by character, line by line, and stops when a non-matching character is found or a word ends to return the longest prefix found.
Method 3: Divide and Conquer
The Divide and Conquer method splits the list of words into two halves, finds the longest common prefix for each half, and then merges the two prefixes. This approach follows the classic divide and conquer algorithmic paradigm.
Here’s an example:
def common_prefix(left, right):
min_len = min(len(left), len(right))
for i in range(min_len):
if left[i] != right[i]:
return left[:i]
return left[:min_len]
def longest_common_prefix(strs):
if not strs:
return ""
if len(strs) == 1:
return strs[0]
mid = len(strs) // 2
lcp_left = longest_common_prefix(strs[:mid])
lcp_right = longest_common_prefix(strs[mid:])
return common_prefix(lcp_left, lcp_right)
print(longest_common_prefix(["flower","flow","flight"]))
Output: “fl”
This method uses recursion to divide the original problem into subproblems, solves each subproblem, and combines the results to find the longest common prefix.
Method 4: Binary Search
The Binary Search method finds the longest common prefix by performing a binary search over the length of the shortest string in the array. It is efficient in cases where long common prefixes are rare.
Here’s an example:
def is_common_prefix(strs, length):
str1 = strs[0][:length]
return all(s.startswith(str1) for s in strs)
def longest_common_prefix(strs):
if not strs:
return ""
min_length = min(len(s) for s in strs)
low, high = 1, min_length
while low <= high:
mid = (low + high) // 2
if is_common_prefix(strs, mid):
low = mid + 1
else:
high = mid - 1
return strs[0][:(low + high) // 2]
print(longest_common_prefix(["flower","flow","flight"]))
Output: “fl”
Using binary search, the method compares the middle prefix of the shortest string in the array to other strings. If the middle prefix is also a prefix of other strings, the search continues to the right half, otherwise, it continues to the left half.
Bonus One-Liner Method 5: Using Python’s Min and Max on Strings
Python’s built-in min and max functions can find the smallest and largest string in an array. The common prefix of these two strings is also the longest common prefix of the array due to the lexicographical order of strings.
Here’s an example:
def longest_common_prefix(strs):
if not strs:
return ""
s1 = min(strs)
s2 = max(strs)
for i, c in enumerate(s1):
if c != s2[i]:
return s1[:i]
return s1
print(longest_common_prefix(["flower","flow","flight"]))
Output: “fl”
This concise one-liner method takes advantage of Python’s string comparison to determine the longest common prefix efficiently.
Summary/Discussion
- Method 1: Horizontal Scanning. Straightforward. Intuitive. Potentially inefficient for large arrays with short prefixes.
- Method 2: Vertical Scanning. Efficient for early mismatches. Can handle cases with very short prefixes efficiently. Might still require scans of many characters.
- Method 3: Divide and Conquer. Elegant and follows a classic algorithmic approach. Recursion adds overhead and may be overkill for small datasets.
- Method 4: Binary Search. Utilizes binary search efficiency. Good for long prefixes. Not as direct or intuitive as other methods.
- Bonus Method 5: Min/Max One-Liner. Extremely concise and makes use of Python’s native functions. May not be as efficient for large arrays with very long words.