The Longest Common Prefix problem on Leetcode is a classic string manipulation problem. Here’s the problem statement:
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 "".
Examples:
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.Naive Solution: Compare Characters Iteratively
Approach:
- Start with the first string as the prefix.
- Iterate over each character position of the first string.
- For each character, check if all other strings have the same character at the same position.
- Stop when a mismatch is found or when the end of any string is reached.
Code:
public class LongestCommonPrefix {
public static String longestCommonPrefixNaive(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
int prefixLength = prefix.length();
for (int i = 0; i < prefixLength; i++) {
char c = prefix.charAt(i);
for (int j = 1; j < strs.length; j++) {
if (i >= strs[j].length() || strs[j].charAt(i) != c) {
return prefix.substring(0, i);
}
}
}
return prefix;
}
public static void main(String[] args) {
String[] strs = {"flower", "flow", "flight"};
System.out.println("Longest Common Prefix: " + longestCommonPrefixNaive(strs));
}
}Time Complexity:
- Outer loop: Runs up to
Ltimes, whereLis the length of the shortest string. - Inner loop: Runs
n-1times for each character (n= number of strings).
Overall: O(L×n)O(L \times n)O(L×n).
Space Complexity:
- O(1)O(1)O(1), as no extra space is used.
Horizontal Scanning Solution
Approach:
- Start with the first string as the prefix.
- Compare the prefix with each string in the array.
- Shorten the prefix as necessary until all strings share the common prefix.
Code:
public class LongestCommonPrefix {
public static String longestCommonPrefixHorizontal(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
return prefix;
}
public static void main(String[] args) {
String[] strs = {"flower", "flow", "flight"};
System.out.println("Longest Common Prefix: " + longestCommonPrefixHorizontal(strs));
}
}Time Complexity:
- Comparing the prefix with each string takes O(L)O(L)O(L), where LLL is the prefix length.
- For nnn strings: O(L×n)O(L \times n)O(L×n).
Space Complexity:
- O(1)O(1)O(1).
Vertical Scanning Solution
Approach:
- Compare characters column by column.
- Stop when a mismatch occurs.
Code:
public class LongestCommonPrefix {
public static String longestCommonPrefixVertical(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++) {
if (i >= strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
public static void main(String[] args) {
String[] strs = {"flower", "flow", "flight"};
System.out.println("Longest Common Prefix: " + longestCommonPrefixVertical(strs));
}
}Time Complexity:
- O(L×n)O(L \times n)O(L×n), where LLL is the length of the shortest string.
Space Complexity:
- O(1)O(1)O(1).
Optimized Solution: Divide and Conquer
Approach:
- Divide the array into two halves.
- Recursively find the longest common prefix for each half.
- Merge the results.
Code:
public class LongestCommonPrefix {
public static String longestCommonPrefixDivideAndConquer(String[] strs) {
if (strs == null || strs.length == 0) return "";
return findPrefix(strs, 0, strs.length - 1);
}
private static String findPrefix(String[] strs, int left, int right) {
if (left == right) {
return strs[left];
}
int mid = (left + right) / 2;
String lcpLeft = findPrefix(strs, left, mid);
String lcpRight = findPrefix(strs, mid + 1, right);
return commonPrefix(lcpLeft, lcpRight);
}
private static String commonPrefix(String left, String right) {
int minLength = Math.min(left.length(), right.length());
for (int i = 0; i < minLength; i++) {
if (left.charAt(i) != right.charAt(i)) {
return left.substring(0, i);
}
}
return left.substring(0, minLength);
}
public static void main(String[] args) {
String[] strs = {"flower", "flow", "flight"};
System.out.println("Longest Common Prefix: " +
longestCommonPrefixDivideAndConquer(strs));
}
}Time Complexity:
- The array is divided into two halves logn\log nlogn times.
- At each level, the
commonPrefixfunction compares LLL characters.
Overall: O(L×n)O(L \times n)O(L×n).
Space Complexity:
- O(logn)O(\log n)O(logn) due to recursion stack.
Optimized Solution: Binary Search
Approach:
- Find the minimum string length.
- Use binary search to determine the longest prefix length.
Code:
public class LongestCommonPrefix {
public static String longestCommonPrefixBinarySearch(String[] strs) {
if (strs == null || strs.length == 0) return "";
int minLength = Integer.MAX_VALUE;
for (String str : strs) {
minLength = Math.min(minLength, str.length());
}
int low = 1, high = minLength;
while (low <= high) {
int mid = (low + high) / 2;
if (isCommonPrefix(strs, mid)) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return strs[0].substring(0, (low + high) / 2);
}
private static boolean isCommonPrefix(String[] strs, int length) {
String prefix = strs[0].substring(0, length);
for (int i = 1; i < strs.length; i++) {
if (!strs[i].startsWith(prefix)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String[] strs = {"flower", "flow", "flight"};
System.out.println("Longest Common Prefix: " +
longestCommonPrefixBinarySearch(strs));
}
}Time Complexity:
- Binary search takes O(logL)O(\log L)O(logL), and each check takes O(n)O(n)O(n).
Overall: O(n×logL)O(n \times \log L)O(n×logL).
Space Complexity:
- O(1)O(1)O(1).
Conclusion
Each approach offers a trade-off between complexity and implementation simplicity:
- Naive and Horizontal Scanning: Simple to implement but not the most efficient.
- Vertical Scanning: Easier to understand and slightly more efficient.
- Divide and Conquer: Good for larger datasets but uses recursion.
- Binary Search: Efficient but slightly harder to implement.
Choose the method based on your needs and the dataset size.