StringProblem 27 of 43
Longest Common Prefix
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 "".
Example 1:
- Input: strs = ["flower", "flow", "flight"]
- Output: "fl"
Example 2:
- Input: strs = ["dog", "racecar", "car"]
- Output: ""
- Explanation: No common prefix exists
Approach 1: Horizontal Scanning (Brute Force)
Intuition
Start with the first string as the prefix. Compare it with each subsequent string, reducing the prefix until it matches or becomes empty.
Algorithm
- Take the first string as the initial prefix
- For each subsequent string, shrink the prefix until it matches
- If prefix becomes empty, return ""
- Return the final prefix
java
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
// Reduce prefix until it matches the start of current string
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
return prefix;
}
}Complexity Analysis
- Time Complexity: O(S) where S is the sum of all characters in all strings
- Space Complexity: O(1) - only using constant extra space
Approach 2: Vertical Scanning
Intuition
Compare characters column by column (vertically). Stop when we find a mismatch or reach the end of any string.
Algorithm
- Iterate through characters of the first string (column by column)
- For each position, check if all strings have the same character
- If mismatch or end of any string, return prefix so far
- If all characters match, include it in prefix
java
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
for (int i = 0; i < strs[0].length(); i++) {
char c = strs[0].charAt(i);
for (int j = 1; j < strs.length; j++) {
// Check if we've reached end of current string or mismatch
if (i >= strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}
}
}
// First string is the common prefix
return strs[0];
}
}Complexity Analysis
- Time Complexity: O(S) where S is the sum of all characters, but performs better when common prefix is small
- Space Complexity: O(1)
Approach 3: Divide and Conquer
Intuition
Divide the array into two halves, find LCP in each half recursively, then find LCP of the two results.
Algorithm
- Recursively divide the array into two halves
- Find LCP of left half and right half
- Merge by finding LCP of the two results
- Base case: single string returns itself
java
public class Solution {
private String commonPrefix(String left, String right) {
int minLen = Math.min(left.length(), right.length());
for (int i = 0; i < minLen; i++) {
if (left.charAt(i) != right.charAt(i)) {
return left.substring(0, i);
}
}
return left.substring(0, minLen);
}
private String lcpHelper(String[] strs, int left, int right) {
if (left == right) {
return strs[left];
}
int mid = left + (right - left) / 2;
String lcpLeft = lcpHelper(strs, left, mid);
String lcpRight = lcpHelper(strs, mid + 1, right);
return commonPrefix(lcpLeft, lcpRight);
}
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
return lcpHelper(strs, 0, strs.length - 1);
}
}Complexity Analysis
- Time Complexity: O(S) - Each character compared once
- Space Complexity: O(m * log n) - Recursion stack depth is log n, each level stores up to m characters
Approach 4: Binary Search
Intuition
Binary search on the length of the common prefix. Check if a prefix of given length is common to all strings.
java
public class Solution {
private boolean isCommonPrefix(String[] strs, int len) {
String prefix = strs[0].substring(0, len);
for (int i = 1; i < strs.length; i++) {
if (!strs[i].startsWith(prefix)) {
return false;
}
}
return true;
}
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
int minLen = Integer.MAX_VALUE;
for (String s : strs) {
minLen = Math.min(minLen, s.length());
}
int low = 0, high = minLen;
while (low < high) {
int mid = (low + high + 1) / 2;
if (isCommonPrefix(strs, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return strs[0].substring(0, low);
}
}Complexity Analysis
- Time Complexity: O(S * log m) where m is the minimum string length
- Space Complexity: O(1)
Approach 5: Sort and Compare (Clever)
Intuition
Sort the array. The LCP of the entire array must be the LCP of just the first and last strings (lexicographically smallest and largest).
java
import java.util.Arrays;
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
Arrays.sort(strs);
String first = strs[0];
String last = strs[strs.length - 1];
int i = 0;
while (i < first.length() && i < last.length()
&& first.charAt(i) == last.charAt(i)) {
i++;
}
return first.substring(0, i);
}
}Complexity Analysis
- Time Complexity: O(n * m * log n) - Sorting dominates
- Space Complexity: O(1) or O(n) depending on sorting algorithm
Key Takeaways
- Vertical scanning is often most efficient when common prefix is short
- Sorting trick is clever but adds O(n log n) overhead
- Binary search approach is useful when LCP could be long
- All approaches achieve O(S) worst case where S is total characters
- Choose based on expected input characteristics
- This is a classic LeetCode easy problem but has multiple elegant solutions