Longest Common Prefix
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:
Example 2:
Explanation: There is no common prefix among the input strings.
Constraints:
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]consists of only lowercase English letters if it is non-empty.
Solve it on LeetCode
Approaches
Approach 1: Horizontal Scanning
Intuition:
This approach involves taking the first string in the array and comparing it with each subsequent string. For each comparison, the common prefix is updated. By the end of this systematic pairwise comparison of strings, we derive the overall longest common prefix.
Code:
- Time Complexity: O(S), where S is the sum of all characters in the input strings.
- Space Complexity: O(1), as we are only using a constant amount of extra space.
Approach 2: Vertical Scanning
Intuition:
This method works by checking each character position across all input strings, proceeding character by character. This approach terminates when a mismatch is found or when one string is exhausted.
Code:
- Time Complexity: O(S), where S is the sum of all characters in all strings.
- Space Complexity: O(1), as we are only using a constant amount of extra space.
Approach 3: Divide and Conquer
Intuition:
The divide and conquer approach breaks the problem into smaller sub-problems. It recursively divides the array into two halves until it reduces to the smallest size, then it combines the results by finding a common prefix between two halves.
Code:
- Time Complexity: O(S), where S is the sum of all characters in all strings. In the worst case, we are dividing every string in two substrings.
- Space Complexity: O(m log n), where m is the number of strings. This complexity arises due to the recursive call stack.
Approach 4: Binary Search
Intuition:
This approach uses binary search on the length of the common prefix. It checks a middle value to see if all strings have a common prefix of that length. If they do, the length is increased; otherwise, it is decreased, effectively narrowing down the range.
Code:
- Time Complexity: O(S log m), where m is the length of the smallest string and S is the sum of all characters in all strings since checking if a prefix is common is O(S).
- Space Complexity: O(1).